Trees, traversals and binary search trees

Implement the four traversals iteratively and recursively, use BST ordering, and find the lowest common ancestor without extra structure.

Depth-first and breadth-first

from collections import deque
from dataclasses import dataclass, field

@dataclass
class Node:
    value: int
    left: "Node | None" = None
    right: "Node | None" = None


def preorder(root: Node | None) -> list[int]:
    """Root, left, right: use it to copy or serialise a tree."""
    out: list[int] = []
    stack = [root] if root else []
    while stack:
        node = stack.pop()
        out.append(node.value)
        if node.right:
            stack.append(node.right)     # push right first so left pops first
        if node.left:
            stack.append(node.left)
    return out


def inorder(root: Node | None) -> list[int]:
    """Left, root, right: sorted order for a binary search tree."""
    out: list[int] = []
    stack: list[Node] = []
    current = root
    while current or stack:
        while current:                   # descend to the leftmost node
            stack.append(current)
            current = current.left
        node = stack.pop()
        out.append(node.value)
        current = node.right
    return out


def postorder(root: Node | None) -> list[int]:
    """Left, right, root: children before parents, as a free requires."""
    if root is None:
        return []
    out, stack = [], [(root, False)]
    while stack:
        node, visited = stack.pop()
        if visited:
            out.append(node.value)
        else:
            stack.append((node, True))
            if node.right:
                stack.append((node.right, False))
            if node.left:
                stack.append((node.left, False))
    return out


def level_order(root: Node | None) -> list[list[int]]:
    """Breadth first, one list per level."""
    if root is None:
        return []
    out: list[list[int]] = []
    q = deque([root])
    while q:
        level = []
        for _ in range(len(q)):          # snapshot the level size
            node = q.popleft()
            level.append(node.value)
            if node.left:
                q.append(node.left)
            if node.right:
                q.append(node.right)
        out.append(level)
    return out

• A skewed tree makes the recursive form use O(n) stack, which overflows on a large input. The iterative form with a heap-allocated stack has the same bound but does not blow the call stack.
• Pre-order and post-order are close to mirror images in the iterative form; the visited flag is what makes post-order correct without a second stack.
• Level order is the right traversal whenever the answer is a distance: minimum depth, connecting siblings, or the right-hand view.

Binary search tree properties

def validate_bst(root: Node | None) -> bool:
    """Pass a range down: checking only the parent is the classic mistake."""
    def check(node: Node | None, low: float, high: float) -> bool:
        if node is None:
            return True
        if not (low < node.value < high):
            return False
        return (check(node.left, low, node.value) and
                check(node.right, node.value, high))
    return check(root, float("-inf"), float("inf"))


def search_bst(root: Node | None, target: int) -> Node | None:
    while root is not None:              # iterative: no stack growth
        if target == root.value:
            return root
        root = root.left if target < root.value else root.right
    return None


def kth_smallest(root: Node | None, k: int) -> int:
    """In-order position k. O(h) space, and O(k) time with early exit."""
    stack: list[Node] = []
    current = root
    while True:
        while current:
            stack.append(current)
            current = current.left
        node = stack.pop()
        k -= 1
        if k == 0:
            return node.value
        current = node.right


def lowest_common_ancestor(root: Node, p: Node, q: Node) -> Node:
    """Works on any binary tree: the first node where the two split."""
    if root in (p, q):
        return root
    left = lowest_common_ancestor(root.left, p, q) if root.left else None
    right = lowest_common_ancestor(root.right, p, q) if root.right else None
    if left and right:
        return root                      # p and q are on different sides
    return left or right


def lca_bst(root: Node, p: int, q: int) -> Node:
    """With a BST, the split is decided by the values, so no recursion needed."""
    node = root
    while node:
        if p < node.value and q < node.value:
            node = node.left
        elif p > node.value and q > node.value:
            node = node.right
        else:
            return node                  # this is the split point
    raise ValueError("not found")


def tree_height(root: Node | None) -> int:
    """Post-order: the answer depends on both children."""
    if root is None:
        return 0
    return 1 + max(tree_height(root.left), tree_height(root.right))

A plain BST is only O(log n) if it stays balanced. Inserting sorted data builds a list, and then every operation is O(n). That is why production ordered containers use a red-black or B-tree, and why the balanced-tree discussion is not academic.

Serialising and rebuilding

def serialize(root: Node | None) -> str:
    """Pre-order with explicit nulls: unambiguous, so the shape is preserved."""
    out: list[str] = []

    def walk(node: Node | None) -> None:
        if node is None:
            out.append("#")
            return
        out.append(str(node.value))
        walk(node.left)
        walk(node.right)

    walk(root)
    return ",".join(out)


def deserialize(data: str) -> Node | None:
    tokens = iter(data.split(","))

    def build() -> Node | None:
        token = next(tokens)
        if token == "#":
            return None
        node = Node(int(token))
        node.left = build()
        node.right = build()
        return node

    return build()


def invert(root: Node | None) -> Node | None:
    """Pre-order swap: the children must both exist before the recursion."""
    if root is None:
        return None
    root.left, root.right = root.right, root.left
    invert(root.left)
    invert(root.right)
    return root


if __name__ == "__main__":
    tree = Node(5, Node(3, Node(1), Node(4)), Node(8, Node(7), Node(9)))
    print(inorder(tree))                 # [1, 3, 4, 5, 7, 8, 9]
    print(level_order(tree))
    blob = serialize(tree)
    print(blob)
    print(inorder(deserialize(blob)) == inorder(tree))
    print(validate_bst(tree))
    print(lca_bst(tree, 1, 4).value)     # 3

FAQ

Related

Graph algorithms: BFS, DFS and shortest paths Recursion, backtracking and divide and conquer

Last refreshed 2026-09-18.