Build a Binary Tree

Create a fixed seven-node binary tree and render its shape.

Algorithm

The canonical tree is 4(2(1,3),6(5,7)), so this Scala DSA implementation can be compared directly with the rest of the DSA track.

Basic Implementation

basic.scala

import scala.collection.mutable.{ArrayBuffer, Queue}
class Node(val value: Int, var left: Node = null, var right: Node = null)
object Main {
  def render(node: Node): String = {
    if (node == null) "_"
    else if (node.left == null && node.right == null) node.value.toString
    else s"${node.value}(${render(node.left)},${render(node.right)})"
  }
  def sampleTree(): Node = new Node(4, new Node(2, new Node(1), new Node(3)), new Node(6, new Node(5), new Node(7)))
  def listString(values: Seq[Int]): String = values.mkString("[", ", ", "]")
  def main(args: Array[String]): Unit = { println(render(sampleTree())) }
}

Complexity

Time: O(n)
Space: O(n)

Implementation notes

class Node(val value: Int, var left: Node = null, var right: Node = null) uses an immutable Int value with mutable child references.
Empty children are represented with null defaults, not Option[Node].
sampleTree() builds the whole tree with nested constructors: new Node(4, new Node(2, ...), new Node(6, ...)).
There are no later child assignments in this lesson; the left and right links are wired as constructor arguments.
The trace shows the construction visually from children upward: 1, 3, then 2(1,3), followed by 5, 7, then 6(5,7), and finally the root 4(2(1,3),6(5,7)).
render(node) treats null as _, prints leaf nodes as just their value, and prints internal nodes as value(left,right).
main calls println(render(sampleTree())), so the checked output is the compact tree string 4(2(1,3),6(5,7)).

node links A node stores one value plus references to its left and right children.