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.

Basic Implementation

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

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.
preorder Preorder records the current node before visiting left and right subtrees.