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 Python 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.py
Replay: real traced execution (multi-file project)
class Node:
    def __init__(self, value, left=None, right=None):
        self.value = value
        self.left = left
        self.right = right

def render(node):
    if node is None:
        return "_"
    if node.left is None and node.right is None:
        return str(node.value)
    return f"{node.value}({render(node.left)},{render(node.right)})"

def sample_tree():
    n1 = Node(1)
    n3 = Node(3)
    n2 = Node(2, n1, n3)
    n5 = Node(5)
    n7 = Node(7)
    n6 = Node(6, n5, n7)
    return Node(4, n2, n6)

root = sample_tree()
print(render(root))

  1. node ← 1, tree ← 1

    20n6 = Node(6, n5, n7)21return Node(4, n2, n6)
    values this step1node1tree

  2. node ← 3, tree ← 1, 3

    20n6 = Node(6, n5, n7)21return Node(4, n2, n6)
    values this step3node1, 3tree

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

    20n6 = Node(6, n5, n7)21return Node(4, n2, n6)
    values this step2node2(1,3)tree

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

    20n6 = Node(6, n5, n7)21return Node(4, n2, n6)
    values this step5node2(1,3), 5tree

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

    20n6 = Node(6, n5, n7)21return Node(4, n2, n6)
    values this step7node2(1,3), 5, 7tree

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

    20n6 = Node(6, n5, n7)21return Node(4, n2, n6)
    values this step6node2(1,3), 6(5,7)tree

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

    20n6 = Node(6, n5, n7)21return Node(4, n2, n6)
    values this step4node4(2(1,3),6(5,7))tree

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

    23root = sample_tree()24print(render(root))
    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

  • Python represents each tree node as a Node object with value, left, and right attributes. The constructor defaults left and right to None, which marks missing leaves for render.
  • sample_tree() allocates leaf nodes first, then passes those object references into parent constructors such as Node(2, n1, n3) and Node(6, n5, n7) before returning the root Node(4, n2, n6).
  • There is no queue or builder state during construction; the replay-visible structure comes from explicit child assignments and the final recursive render(root) call. Python manages the allocated nodes while they remain reachable from root.