Binary Trees and BSTs: Traversals, Recursion Depth, Validation and Serialization

By 0xmote · May 25, 2026 · 18 min read · Updated Sep 27, 2026 Intermediate Tutorial

Key takeaways

Most tree bugs come from three misunderstandings: the BST rule applies to entire subtrees, not just children; a tree's height, not its size, decides recursion depth and search cost; and a traversal order alone does not identify a tree. This guide covers traversals (recursive and iterative), level order with a queue, BST insert/search/delete and validation, LCA and diameter, and how to serialize a tree so it round-trips.

Introduction

A tree is a connected graph with no cycles, usually drawn with one node chosen as the root. Every node except the root has exactly one parent, which is what makes trees easy to process recursively: a tree is a root plus some smaller trees.

That recursive picture is also where the common bugs come from. Code that treats a tree as “a node and its children” misses properties that hold over whole subtrees. Code that assumes a tree is shallow crashes on a tree that is actually a long chain. This article covers the traversals and the binary search tree (BST) operations you need for interviews, with attention to the invariants each one relies on and the inputs that break them.

Terms That Change the Answer

        1        <- root, depth 0
       / \
      2   3      <- depth 1
     / \
    4   5        <- leaves, depth 2

Depth of a node: edges from the root to it. Node 4 has depth 2.
Height of a tree: the longest root-to-leaf path. Be careful with the unit. Counting edges gives 2 here; counting nodes gives 3. LeetCode 104 (Maximum Depth) counts nodes, so the answer for this tree is 3. Many textbooks count edges. Read which one the problem wants.
Full binary tree: every node has 0 or 2 children. Complete: every level is filled except possibly the last, which is filled from the left (the shape of a binary heap). Perfect: all leaves at the same depth.
Balanced: height stays O(log n). A tree of n nodes has height at least about log2(n) and at most n. Where it lands between those two decides how fast search is and how deep recursion goes.

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def sample():
    return TreeNode(1, TreeNode(2, TreeNode(4), TreeNode(5)), TreeNode(3))

Depth-First Traversals

The three depth-first orders differ only in when the node itself is recorded relative to its subtrees:

def preorder(root):
    out = []
    def visit(node):
        if node is None:
            return
        out.append(node.val)   # node, then left, then right
        visit(node.left)
        visit(node.right)
    visit(root)
    return out

def inorder(root):
    out = []
    def visit(node):
        if node is None:
            return
        visit(node.left)
        out.append(node.val)   # left, node, right
        visit(node.right)
    visit(root)
    return out

def postorder(root):
    out = []
    def visit(node):
        if node is None:
            return
        visit(node.left)
        visit(node.right)
        out.append(node.val)   # left, right, node
    visit(root)
    return out

root = sample()
print(preorder(root))   # [1, 2, 4, 5, 3]
print(inorder(root))    # [4, 2, 5, 1, 3]
print(postorder(root))  # [4, 5, 2, 3, 1]

Which order to use follows from what the node needs:

Preorder when the node’s work must happen before its children see it: copying a tree, passing a path or a bound down, serialization.
Inorder when you want a BST’s values in sorted order.
Postorder when the node’s answer depends on its children’s answers: height, subtree sums, diameter, deleting a tree.

A note on a popular one-liner: return [node.val] + preorder(node.left) + preorder(node.right) is correct but copies lists at every level. Each value is copied once per ancestor, so the total cost is O(n x height), which is O(n²) on a skewed tree. Appending to a shared list, as above, keeps it O(n).

Recursion depth is tree height

The call stack grows one frame per level, so recursion depth equals the height of the tree. On a balanced tree of a million nodes that is about 20 frames. On a chain it is a million.

import sys

def chain(n):
    head = TreeNode(0)
    node = head
    for i in range(1, n):
        node.right = TreeNode(i)
        node = node.right
    return head

def max_depth(node):
    if node is None:
        return 0
    return 1 + max(max_depth(node.left), max_depth(node.right))

print(sys.getrecursionlimit())  # 1000
print(max_depth(chain(900)))    # 900
try:
    max_depth(chain(5000))
except RecursionError as e:
    print("RecursionError:", e)  # RecursionError: maximum recursion depth exceeded

Chains are not exotic test data. They are exactly what you get from inserting sorted keys into a plain BST, and judges include them precisely because they break recursive solutions. sys.setrecursionlimit pushes the problem further out, but CPython’s frames still live on the C stack, and a high enough limit can crash the process with a segmentation fault instead of raising a catchable error.

Iterative traversals with an explicit stack

def preorder_iterative(root):
    out, stack = [], [root] if root else []
    while stack:
        node = stack.pop()
        out.append(node.val)
        if node.right:            # pushed first, popped last
            stack.append(node.right)
        if node.left:
            stack.append(node.left)
    return out

def inorder_iterative(root):
    out, stack = [], []
    node = root
    while node or stack:
        while node:               # walk as far left as possible
            stack.append(node)
            node = node.left
        node = stack.pop()        # leftmost unvisited node
        out.append(node.val)
        node = node.right         # then its right subtree
    return out

def postorder_iterative(root):
    # Produce node-right-left, then reverse to get left-right-node
    out, stack = [], [root] if root else []
    while stack:
        node = stack.pop()
        out.append(node.val)
        if node.left:
            stack.append(node.left)
        if node.right:
            stack.append(node.right)
    return out[::-1]

print(preorder_iterative(root), inorder_iterative(root), postorder_iterative(root))
# [1, 2, 4, 5, 3] [4, 2, 5, 1, 3] [4, 5, 2, 3, 1]
print(len(inorder_iterative(chain(100000))))  # 100000

The inorder version is the one worth memorizing, because it also lets you stop early: the k-th smallest element of a BST (LeetCode 230) is the k-th pop, and you never visit the rest of the tree. The reversed-postorder trick is simple but produces the whole output before reversing, so it cannot be used when you need to act on each node in postorder as you go. For that, keep a (node, visited) flag on the stack and emit a node the second time you pop it.

Level Order: BFS With a Queue

Breadth-first traversal visits the tree one level at a time. The trick for grouping by level is to read the queue length at the start of each level: exactly that many nodes belong to it.

from collections import deque

def level_order(root):
    if root is None:
        return []
    levels, queue = [], deque([root])
    while queue:
        level = []
        for _ in range(len(queue)):   # len is evaluated once, before the loop
            node = queue.popleft()
            level.append(node.val)
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
        levels.append(level)
    return levels

print(level_order(root))                       # [[1], [2, 3], [4, 5]]
print([lvl[-1] for lvl in level_order(root)])  # [1, 3, 5]  right side view

Use collections.deque. list.pop(0) shifts every remaining element, turning an O(n) traversal into O(n²) on wide trees. BFS also has no recursion, so it is a safe way to compute height on a chain of any length.

BFS is the right tool whenever the answer is “the first level where something happens”. Minimum depth (LeetCode 111) is the classic case, and its recursive version has a trap:

def min_depth_wrong(node):
    if node is None:
        return 0
    return 1 + min(min_depth_wrong(node.left), min_depth_wrong(node.right))

def min_depth(root):
    if root is None:
        return 0
    queue = deque([(root, 1)])
    while queue:
        node, depth = queue.popleft()
        if node.left is None and node.right is None:
            return depth              # first leaf found is the shallowest
        if node.left:
            queue.append((node.left, depth + 1))
        if node.right:
            queue.append((node.right, depth + 1))

lopsided = TreeNode(1, None, TreeNode(2, None, TreeNode(3)))
print(min_depth_wrong(lopsided), min_depth(lopsided))  # 1 3

The wrong version treats a missing child as a leaf at depth 0, so a node with only a right child reports depth 1. Minimum depth is measured to a leaf, and a node with one child is not a leaf. The BFS version also stops as soon as it reaches the shallowest leaf instead of exploring the whole tree.

Binary Search Trees

The invariant is about subtrees

A BST requires that for every node, all values in its left subtree are smaller and all values in its right subtree are larger. That single rule is what makes search work: at each node you can discard an entire subtree. It is also why the inorder traversal of a BST is sorted.

You also have to decide what to do with duplicates. The code below ignores them, which makes the tree a set. Alternatives are a count field per node or a consistent rule such as “equal goes right”; mixing rules between insert and search is a source of “value inserted but not found” bugs.

def insert(root, val):
    new = TreeNode(val)
    if root is None:
        return new
    node = root
    while True:
        if val < node.val:
            if node.left is None:
                node.left = new
                return root
            node = node.left
        elif val > node.val:
            if node.right is None:
                node.right = new
                return root
            node = node.right
        else:
            return root  # duplicate: ignore

def search(root, val):
    node = root
    while node and node.val != val:
        node = node.left if val < node.val else node.right
    return node

def build(values):
    root = None
    for v in values:
        root = insert(root, v)
    return root

Iterative insert and search avoid the recursion-depth problem entirely, and they are no longer than the recursive versions.

Height decides the cost

Search, insert and delete are O(h), where h is the height. What h is depends entirely on insertion order:

import random

def height(root):
    if root is None:
        return 0
    best, stack = 0, [(root, 1)]
    while stack:
        node, d = stack.pop()
        best = max(best, d)
        if node.left:
            stack.append((node.left, d + 1))
        if node.right:
            stack.append((node.right, d + 1))
    return best

n = 1000
print(height(build(range(n))))   # 1000: every node is a right child
vals = list(range(n))
random.Random(42).shuffle(vals)
print(height(build(vals)))       # 21 for this shuffle

Sorted input produces a linked list. A random order produces a tree whose height is a small multiple of log2(n) (about 10 for n = 1000), but “random order” is not something you control in real data. Self-balancing trees such as AVL and red-black trees fix this by rotating nodes after each update so that height stays O(log n). Python’s standard library has no balanced BST; in practice people use a sorted list with bisect for mostly-static data, or the third-party sortedcontainers package. Java’s TreeMap and C++‘s std::map are red-black trees.

Deleting a node with two children

Deleting a leaf or a node with one child is a pointer change. With two children, copy in the inorder successor (the smallest value in the right subtree), then delete the successor from the right subtree. The successor has no left child, so that second deletion is one of the easy cases.

def delete(root, val):
    if root is None:
        return None
    if val < root.val:
        root.left = delete(root.left, val)
    elif val > root.val:
        root.right = delete(root.right, val)
    else:
        if root.left is None:
            return root.right
        if root.right is None:
            return root.left
        succ = root.right
        while succ.left:
            succ = succ.left
        root.val = succ.val
        root.right = delete(root.right, succ.val)
    return root

t = build([5, 3, 7, 2, 4, 6, 8])
print(inorder_iterative(t))          # [2, 3, 4, 5, 6, 7, 8]
t = delete(t, 5)
print(t.val, inorder_iterative(t))   # 6 [2, 3, 4, 6, 7, 8]

Checking the inorder sequence after every delete in a test is a cheap way to confirm the invariant survived.

Validating a BST

This is the problem where the “subtree, not child” distinction bites:

def is_valid_bst_wrong(node):
    if node is None:
        return True
    if node.left and node.left.val >= node.val:
        return False
    if node.right and node.right.val <= node.val:
        return False
    return is_valid_bst_wrong(node.left) and is_valid_bst_wrong(node.right)

def is_valid_bst(root):
    stack = [(root, float('-inf'), float('inf'))]
    while stack:
        node, low, high = stack.pop()
        if node is None:
            continue
        if not (low < node.val < high):
            return False
        stack.append((node.left, low, node.val))
        stack.append((node.right, node.val, high))
    return True

#     5
#    / \
#   4   6
#      / \
#     3   7
bad = TreeNode(5, TreeNode(4), TreeNode(6, TreeNode(3), TreeNode(7)))
print(is_valid_bst_wrong(bad), is_valid_bst(bad))  # True False
print(is_valid_bst(TreeNode(2, TreeNode(2), TreeNode(2))))  # False

Node 3 is a valid left child of 6 but lies in the right subtree of 5. The range version passes each node the open interval its value must fall in, narrowing it on the way down. An equivalent check is that the inorder traversal is strictly increasing. Using float('-inf') and float('inf') as initial bounds matters: problems like LeetCode 98 include values at the 32-bit limits, and sentinels like -2**31 fail on a node that actually holds that value.

I have written the child-only version more than once when solving quickly, and it is dangerous precisely because it passes the small examples most problems show. When I review a tree solution now, the first question I ask is whether each check involves only a node and its children, or whether it needs information from further up. If it needs ancestors, the recursion has to carry that information down as parameters.

Problems That Use Postorder Results

Lowest common ancestor

In a BST, the LCA of p and q is the first node where they split to different sides (or the node equals one of them). This needs no recursion:

def lca_bst(root, p, q):
    node = root
    while node:
        if p < node.val and q < node.val:
            node = node.left
        elif p > node.val and q > node.val:
            node = node.right
        else:
            return node

bst = build([6, 2, 8, 0, 4, 7, 9, 3, 5])
print(lca_bst(bst, 2, 8).val, lca_bst(bst, 2, 4).val, lca_bst(bst, 3, 5).val)  # 6 2 4

In a general binary tree there is no ordering to steer by, so each subtree reports whether it contains p or q, and the node where both sides report back is the answer:

def lca(root, p, q):
    if root is None or root is p or root is q:
        return root
    left = lca(root.left, p, q)
    right = lca(root.right, p, q)
    if left and right:
        return root
    return left or right

n4, n5, n3 = TreeNode(4), TreeNode(5), TreeNode(3)
n2 = TreeNode(2, n4, n5)
r = TreeNode(1, n2, n3)
print(lca(r, n4, n5).val, lca(r, n4, n3).val, lca(r, n2, n5).val)  # 2 1 2

This version assumes both nodes are in the tree. If one might be missing, it returns the other node instead of “not found”, so you need a separate existence check.

Diameter: return one thing, record another

The diameter (LeetCode 543) is the longest path between any two nodes, counted in edges. The longest path through a node is its left height plus its right height, but what the node must return to its parent is its height, because a path cannot branch.

def diameter(root):
    best = 0
    def depth(node):
        nonlocal best
        if node is None:
            return 0
        left = depth(node.left)
        right = depth(node.right)
        best = max(best, left + right)   # path through this node
        return 1 + max(left, right)      # height, for the parent
    depth(root)
    return best

print(diameter(r))  # 3

# The longest path need not pass through the root:
deep = TreeNode(1,
    TreeNode(2,
        TreeNode(3, TreeNode(4, TreeNode(5))),
        TreeNode(6, None, TreeNode(7, None, TreeNode(8)))),
    TreeNode(9))
print(diameter(deep))  # 6, the path 5-4-3-2-6-7-8

Returning the diameter instead of the height, or computing only height(root.left) + height(root.right) at the root, are the two submissions that fail. Binary Tree Maximum Path Sum (LeetCode 124) is the same shape with values instead of edge counts, plus the rule that a negative branch should contribute 0.

Serializing a Tree

A traversal order alone does not identify a tree:

a = TreeNode(1, None, TreeNode(2))
b = TreeNode(2, TreeNode(1), None)
print(inorder(a), inorder(b))  # [1, 2] [1, 2]

To make a string that rebuilds exactly one tree, record the missing children too. Preorder with a null marker is the simplest format, because the first token is always the root and each subtree occupies a contiguous run of tokens:

def serialize(root):
    out, stack = [], [root]
    while stack:
        node = stack.pop()
        if node is None:
            out.append('#')
            continue
        out.append(str(node.val))
        stack.append(node.right)
        stack.append(node.left)
    return ','.join(out)

def deserialize(data):
    tokens = iter(data.split(','))
    def build():
        tok = next(tokens)
        if tok == '#':
            return None
        node = TreeNode(int(tok))
        node.left = build()
        node.right = build()
        return node
    return build()

s = serialize(sample())
print(s)                                # 1,2,4,#,#,5,#,#,3,#,#
print(serialize(deserialize(s)) == s)   # True
print(serialize(a), serialize(b))       # 1,#,2,#,# 2,1,#,#,#

Details that break round trips: a separator is required, because without one 1 followed by 23 and 12 followed by 3 produce the same string; negative numbers and multi-digit values need int() on whole tokens rather than character-by-character parsing; and the recursive deserialize has the same depth limit as any recursive traversal, so for chains of thousands of nodes use an explicit stack. With distinct values, preorder plus inorder (without null markers) also identifies a tree, which is LeetCode 105.

LeetCode’s own display format is level order with nulls, and it is handy to have a builder for it when testing locally:

def deserialize_level(data):
    if not data:
        return None
    tokens = data.split(',')
    root = TreeNode(int(tokens[0]))
    queue, i = deque([root]), 1
    while queue and i < len(tokens):
        node = queue.popleft()
        if tokens[i] != '#':
            node.left = TreeNode(int(tokens[i]))
            queue.append(node.left)
        i += 1
        if i < len(tokens) and tokens[i] != '#':
            node.right = TreeNode(int(tokens[i]))
            queue.append(node.right)
        i += 1
    return root

print(serialize(deserialize_level("1,#,2,#,3")))  # 1,#,2,#,3,#,#

Where Tree Solutions Fail

Local checks for a global property: BST validation against children only.
Recursion on unbounded height: sorted-insert BSTs and chain-shaped test trees; use a stack or queue.
Wrong leaf definition: a node with one child treated as a leaf in minimum depth or root-to-leaf path sums.
Height units: nodes versus edges; diameter is in edges, LeetCode 104 depth is in nodes.
Returning the wrong quantity from postorder: returning the answer where the parent needs the height.
list.pop(0) as a queue: O(n) per pop.
Identity versus value: LCA code that compares node.val == p.val breaks when values repeat; compare nodes with is.

Which traversal for which task

Task	Tool	Cost
Visit every node	Pre/in/postorder or BFS	O(n) time, O(h) stack or O(width) queue
Sorted values from a BST	Inorder	O(n)
Search / insert / delete in a BST	Walk from the root	O(h): O(log n) if balanced, O(n) if skewed
Validate a BST	Pass (low, high) down, or check inorder	O(n)
First level where something holds	BFS with level sizes	O(n) worst case, often less
Answer depends on subtrees	Postorder, return a summary per node	O(n)
Store and rebuild a tree	Preorder with null markers	O(n)

Trees are a special case of graphs, so the traversal ideas carry over directly. Graph Representation covers what changes once cycles and multiple parents are allowed, and BFS vs DFS covers choosing between the two traversals on general graphs.