Trees

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.

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

Basic Implementation

basic.scala
Replay: real traced execution (multi-file project)
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())) }
}

  1. node ← 1, tree ← 1

    8}9def sampleTree(): Node = new Node(4, new Node(2, new Node(1), new Node(3)), new Node(6, new Node(5), new Node(7)))10def listString(values: Seq[Int]): String = values.mkString("[", ", ", "]")
    values this step1node1tree

  2. node ← 3, tree ← 1, 3

    8}9def sampleTree(): Node = new Node(4, new Node(2, new Node(1), new Node(3)), new Node(6, new Node(5), new Node(7)))10def listString(values: Seq[Int]): String = values.mkString("[", ", ", "]")
    values this step3node1, 3tree

  3. node ← 2, tree ← 2(1,3)

    8}9def sampleTree(): Node = new Node(4, new Node(2, new Node(1), new Node(3)), new Node(6, new Node(5), new Node(7)))10def listString(values: Seq[Int]): String = values.mkString("[", ", ", "]")
    values this step2node2(1,3)tree

  4. node ← 5, tree ← 2(1,3), 5

    8}9def sampleTree(): Node = new Node(4, new Node(2, new Node(1), new Node(3)), new Node(6, new Node(5), new Node(7)))10def listString(values: Seq[Int]): String = values.mkString("[", ", ", "]")
    values this step5node2(1,3), 5tree

  5. node ← 7, tree ← 2(1,3), 5, 7

    8}9def sampleTree(): Node = new Node(4, new Node(2, new Node(1), new Node(3)), new Node(6, new Node(5), new Node(7)))10def listString(values: Seq[Int]): String = values.mkString("[", ", ", "]")
    values this step7node2(1,3), 5, 7tree

  6. node ← 6, tree ← 2(1,3), 6(5,7)

    8}9def sampleTree(): Node = new Node(4, new Node(2, new Node(1), new Node(3)), new Node(6, new Node(5), new Node(7)))10def listString(values: Seq[Int]): String = values.mkString("[", ", ", "]")
    values this step6node2(1,3), 6(5,7)tree

  7. node ← 4, tree ← 4(2(1,3),6(5,7))

    8}9def sampleTree(): Node = new Node(4, new Node(2, new Node(1), new Node(3)), new Node(6, new Node(5), new Node(7)))10def listString(values: Seq[Int]): String = values.mkString("[", ", ", "]")
    values this step4node4(2(1,3),6(5,7))tree

  8. stdout ← 4(2(1,3),6(5,7))

    10  def listString(values: Seq[Int]): String = values.mkString("[", ", ", "]")11  def main(args: Array[String]): Unit = { println(render(sampleTree())) }12}
    values this step4(2(1,3),6(5,7))stdout4(2(1,3),6(5,7))tree

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)).