Trees

Preorder Traversal

Visit the root before each subtree, producing root-left-right order.

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.

preorder Preorder records the current node before visiting left and right subtrees.

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()
output = []
def preorder(node):
    if node is None:
        return
    output.append(node.value)
    preorder(node.left)
    preorder(node.right)
preorder(root)
print(output)

  1. tree ← 4(2(1,3),6(5,7)), output ← []

    1class Node:2    def __init__(self, value, left=None, right=None):
    values this step4(2(1,3),6(5,7))tree[]output

  2. output ← [4]

    24output = []25def preorder(node):26    if node is None:
    values this step[] → [4]output4node

  3. output ← [4, 2]

    24output = []25def preorder(node):26    if node is None:
    values this step[4] → [4, 2]output2node

  4. output ← [4, 2, 1]

    24output = []25def preorder(node):26    if node is None:
    values this step[4, 2] → [4, 2, 1]output1node

  5. output ← [4, 2, 1, 3]

    24output = []25def preorder(node):26    if node is None:
    values this step[4, 2, 1] → [4, 2, 1, 3]output3node

  6. output ← [4, 2, 1, 3, 6]

    24output = []25def preorder(node):26    if node is None:
    values this step[4, 2, 1, 3] → [4, 2, 1, 3, 6]output6node

  7. output ← [4, 2, 1, 3, 6, 5]

    24output = []25def preorder(node):26    if node is None:
    values this step[4, 2, 1, 3, 6] → [4, 2, 1, 3, 6, 5]output5node

  8. output ← [4, 2, 1, 3, 6, 5, 7]

    24output = []25def preorder(node):26    if node is None:
    values this step[4, 2, 1, 3, 6, 5] → [4, 2, 1, 3, 6, 5, 7]output7node

  9. print(output)

    31preorder(root)32print(output)
    values this step[4, 2, 1, 3, 6, 5, 7]output

Complexity

  • Time: O(n)
  • Space: O(h) recursion stack

Implementation notes

  • Python stores each tree node as a Node object with value, left, and right attributes. Missing children are represented by None, and the recursive preorder(node) function returns immediately for that base case.
  • The traversal uses normal Python call-stack frames rather than an explicit stack container. Each frame holds its current node reference, appends node.value, then calls preorder(node.left) before preorder(node.right).
  • output is one list shared by all recursive calls and mutated with append(...); the trace shows the replay-visible visit order growing as [4], [4, 2], [4, 2, 1], and finally [4, 2, 1, 3, 6, 5, 7].
  • The traversal allocates the result list and uses call-stack frames; those frames, the list, and the tree nodes are managed by Python while references to them remain.