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 Kotlin DSA implementation can be compared directly with the rest of the DSA track.

Basic Implementation

basic.kt 
class Node(val value: Int, var left: Node? = null, var right: Node? = null)
fun render(node: Node?): String {
    if (node == null) return "_"
    if (node.left == null && node.right == null) return node.value.toString()
    return "${node.value}(${render(node.left)},${render(node.right)})"
}
fun sampleTree() = Node(4, Node(2, Node(1), Node(3)), Node(6, Node(5), Node(7)))
fun listString(values: List<Int>) = values.joinToString(", ", "[", "]")
fun main() { println(render(sampleTree())) }

Complexity

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

Implementation notes

  • Kotlin represents each tree node with class Node(val value: Int, var left: Node? = null, var right: Node? = null), so leaf children default to nullable null links.
  • value is a val, while left and right are mutable var properties; this lesson wires children through constructor arguments and does not mutate them afterward.
  • sampleTree() allocates the fixed tree with nested constructor calls: Node(4, Node(2, Node(1), Node(3)), Node(6, Node(5), Node(7))).
  • The nested construction trace shows 1, 3, parent 2, then 5, 7, parent 6, and finally root 4.
  • render(node: Node?) handles nullable references directly: it returns _ for null, prints a leaf as its Int value, and otherwise recurses into left and right.
  • The trace records construction states from 1, 1, 3, 2(1,3), 2(1,3), 6(5,7), to the full 4(2(1,3),6(5,7)).
  • println(render(sampleTree())) prints 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.