Binary Trees and Tries: DFS, BFS and Prefix Search Templates

A tree is a hierarchy: one root, and every other node has exactly one parent. A binary tree allows each node at most two children. Tree problems test whether you can think recursively, and almost all of them reduce to one of two traversals: depth-first (go down a branch, then backtrack) or breadth-first (level by level). This lesson also covers tries, prefix trees used for autocomplete and prefix matching.

Data Engineers meet trees constantly: nested JSON, directory and object-store prefixes, org charts, category hierarchies and query plans are all trees.

The code blocks share the helpers defined in the first block, so run them in order.

How binary trees work

from collections import deque


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


def from_level_order(values):
    """Build a tree from a level-order list where None marks a missing child."""
    if not values or values[0] is None:
        return None
    root = TreeNode(values[0])
    queue = deque([root])
    i = 1
    while queue and i < len(values):
        node = queue.popleft()
        if i < len(values) and values[i] is not None:
            node.left = TreeNode(values[i])
            queue.append(node.left)
        i += 1
        if i < len(values) and values[i] is not None:
            node.right = TreeNode(values[i])
            queue.append(node.right)
        i += 1
    return root


def to_level_order(root):
    out, queue = [], deque([root])
    while queue:
        node = queue.popleft()
        if node:
            out.append(node.val)
            queue.extend([node.left, node.right])
        else:
            out.append(None)
    while out and out[-1] is None:
        out.pop()
    return out


t = from_level_order([3, 9, 20, None, None, 15, 7])
assert to_level_order(t) == [3, 9, 20, None, None, 15, 7]
assert from_level_order([]) is None

Vocabulary you should use precisely:

Term	Meaning
Root, leaf	The top node; a node with no children
Depth of a node	Edges from the root down to it
Height of a tree	Edges (or nodes, say which) on the longest root-to-leaf path
Balanced	Every node’s subtrees differ in height by at most one, so height is O(log n)
Complete	Every level full except possibly the last, filled from the left (heaps use this)
Full	Every node has 0 or 2 children

Most tree algorithms visit every node once: O(n) time, with O(h) extra space for the recursion stack or explicit stack, where h is the height. h is O(log n) for a balanced tree and O(n) for a skewed one (effectively a linked list), which is why recursion can hit Python’s limit on degenerate trees.

Recognising the pattern

Signal	Technique
“Depth”, “height”, “balanced”, “diameter”, “path sum”	Post-order DFS: compute from children, return up
“Good nodes”, “max so far along the path”, “validate a range”	Pre-order DFS: pass state down
“Level by level”, “right side view”, “minimum depth”, “zigzag”	BFS with a queue, one level at a time
“Same tree”, “subtree”, “mirror”	Simultaneous recursion on two trees
“Construct from traversals”, “serialise”	Pre-order plus markers or in-order indices
“Ancestor of two nodes”	Post-order: return what each subtree found
“Prefix”, “starts with”, “autocomplete”, “dictionary of words”	Trie

Core templates in Python

Depth-first traversals

The three orders differ only in when you record the node.

def preorder(root):            # node, left, right
    return [root.val] + preorder(root.left) + preorder(root.right) if root else []


def inorder(root):             # left, node, right
    return inorder(root.left) + [root.val] + inorder(root.right) if root else []


def postorder(root):           # left, right, node
    return postorder(root.left) + postorder(root.right) + [root.val] if root else []


def inorder_iterative(root):
    out, stack, node = [], [], root
    while stack or node:
        while node:                    # go as far left as possible
            stack.append(node)
            node = node.left
        node = stack.pop()
        out.append(node.val)
        node = node.right
    return out


t = from_level_order([1, 2, 3, 4, 5])
assert preorder(t) == [1, 2, 4, 5, 3]
assert inorder(t) == [4, 2, 5, 1, 3]
assert postorder(t) == [4, 5, 2, 3, 1]
assert inorder_iterative(t) == inorder(t)

The list-concatenation versions are short but copy lists at every level; in an interview, appending to a shared list inside a helper is more efficient. Know the iterative in-order version: it is a common follow-up.

Return values up the tree (post-order)

Ask “if I knew the answer for my left and right subtrees, what would mine be?”.

def max_depth(root):
    if not root:
        return 0
    return 1 + max(max_depth(root.left), max_depth(root.right))


def invert_tree(root):
    if root:
        root.left, root.right = invert_tree(root.right), invert_tree(root.left)
    return root


def is_same_tree(p, q):
    if not p or not q:
        return p is q                     # both None -> True; one None -> False
    return p.val == q.val and is_same_tree(p.left, q.left) and is_same_tree(p.right, q.right)


def is_subtree(root, sub):
    if not sub:
        return True
    if not root:
        return False
    return is_same_tree(root, sub) or is_subtree(root.left, sub) or is_subtree(root.right, sub)


t = from_level_order([3, 9, 20, None, None, 15, 7])
assert max_depth(t) == 3 and max_depth(None) == 0
assert to_level_order(invert_tree(from_level_order([4, 2, 7, 1, 3, 6, 9]))) == [4, 7, 2, 9, 6, 3, 1]
assert is_same_tree(from_level_order([1, 2, 3]), from_level_order([1, 2, 3]))
assert not is_same_tree(from_level_order([1, 2]), from_level_order([1, None, 2]))
assert is_subtree(from_level_order([3, 4, 5, 1, 2]), from_level_order([4, 1, 2]))
assert not is_subtree(from_level_order([3, 4, 5, 1, 2, None, None, None, None, 0]), from_level_order([4, 1, 2]))

Return one thing, track another: diameter, balance, max path sum

Some answers do not pass through the root. The helper returns what the parent needs (a height or a one-sided path) while updating a separate best answer.

def diameter_of_binary_tree(root):
    best = 0

    def height(node):                    # returns height in nodes
        nonlocal best
        if not node:
            return 0
        left, right = height(node.left), height(node.right)
        best = max(best, left + right)   # edges on the longest path through node
        return 1 + max(left, right)

    height(root)
    return best


def is_balanced(root):
    def check(node):                     # height, or -1 if unbalanced
        if not node:
            return 0
        left = check(node.left)
        right = check(node.right)
        if left < 0 or right < 0 or abs(left - right) > 1:
            return -1
        return 1 + max(left, right)

    return check(root) >= 0


def max_path_sum(root):
    best = float("-inf")

    def gain(node):                      # best downward path starting at node
        nonlocal best
        if not node:
            return 0
        left = max(gain(node.left), 0)   # drop negative branches
        right = max(gain(node.right), 0)
        best = max(best, node.val + left + right)
        return node.val + max(left, right)

    gain(root)
    return best


assert diameter_of_binary_tree(from_level_order([1, 2, 3, 4, 5])) == 3
assert diameter_of_binary_tree(from_level_order([1])) == 0
assert is_balanced(from_level_order([3, 9, 20, None, None, 15, 7])) is True
assert is_balanced(from_level_order([1, 2, 2, 3, 3, None, None, 4, 4])) is False
assert max_path_sum(from_level_order([1, 2, 3])) == 6
assert max_path_sum(from_level_order([-10, 9, 20, None, None, 15, 7])) == 42
assert max_path_sum(from_level_order([-3])) == -3

Returning −1 as an “unbalanced” signal lets is_balanced stop early and stay O(n); calling a separate height function at every node would be O(n²) on a skewed tree.

Pass state down (pre-order)

def good_nodes(root):
    def visit(node, max_so_far):
        if not node:
            return 0
        good = 1 if node.val >= max_so_far else 0
        new_max = max(max_so_far, node.val)
        return good + visit(node.left, new_max) + visit(node.right, new_max)

    return visit(root, float("-inf"))


assert good_nodes(from_level_order([3, 1, 4, 3, None, 1, 5])) == 4
assert good_nodes(from_level_order([3, 3, None, 4, 2])) == 3
assert good_nodes(from_level_order([1])) == 1

Breadth-first: level by level

Process exactly len(queue) nodes per iteration; that batch is one level.

def level_order(root):
    if not root:
        return []
    levels, queue = [], deque([root])
    while queue:
        level = []
        for _ in range(len(queue)):          # only the nodes of the current level
            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


def right_side_view(root):
    return [level[-1] for level in level_order(root)]


assert level_order(from_level_order([3, 9, 20, None, None, 15, 7])) == [[3], [9, 20], [15, 7]]
assert level_order(None) == []
assert right_side_view(from_level_order([1, 2, 3, None, 5, None, 4])) == [1, 3, 4]
assert right_side_view(from_level_order([1, 2, 3, 4])) == [1, 3, 4]

The last test is the trap in Right Side View: the rightmost node of a level may be in the left subtree.

Lowest common ancestor

Each call returns the target it found in its subtree (or None). The first node where both sides report something is the lowest common ancestor.

def lowest_common_ancestor(root, p, q):
    if root is None or root is p or root is q:
        return root
    left = lowest_common_ancestor(root.left, p, q)
    right = lowest_common_ancestor(root.right, p, q)
    if left and right:
        return root                    # p and q are on different sides
    return left or right


def find(root, val):
    if not root:
        return None
    if root.val == val:
        return root
    return find(root.left, val) or find(root.right, val)


t = from_level_order([3, 5, 1, 6, 2, 0, 8, None, None, 7, 4])
assert lowest_common_ancestor(t, find(t, 5), find(t, 1)).val == 3
assert lowest_common_ancestor(t, find(t, 5), find(t, 4)).val == 5     # a node is its own ancestor
assert lowest_common_ancestor(t, find(t, 7), find(t, 8)).val == 3

This version assumes both nodes exist in the tree. If they might not, track whether each was actually found.

Build from pre-order and in-order traversals

Pre-order’s first value is the root; its position in the in-order list splits the left and right subtrees.

def build_tree(preorder_vals, inorder_vals):
    index_of = {v: i for i, v in enumerate(inorder_vals)}     # values must be unique
    pre_iter = iter(preorder_vals)

    def build(lo, hi):                     # subtree uses inorder_vals[lo:hi]
        if lo >= hi:
            return None
        root_val = next(pre_iter)
        mid = index_of[root_val]
        node = TreeNode(root_val)
        node.left = build(lo, mid)         # left must be built first: pre-order is node, left, right
        node.right = build(mid + 1, hi)
        return node

    return build(0, len(inorder_vals))


t = build_tree([3, 9, 20, 15, 7], [9, 3, 15, 20, 7])
assert to_level_order(t) == [3, 9, 20, None, None, 15, 7]
assert build_tree([], []) is None

The dictionary of in-order positions makes this O(n); searching the list each time with .index() would make it O(n²).

Serialise and deserialise

Pre-order with an explicit marker for missing children captures the exact shape.

def serialize(root):
    out = []

    def visit(node):
        if not node:
            out.append("#")
            return
        out.append(str(node.val))
        visit(node.left)
        visit(node.right)

    visit(root)
    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()


for shape in ([1, 2, 3, None, None, 4, 5], [], [-1], [1, None, 2, None, 3]):
    tree = from_level_order(shape)
    assert to_level_order(deserialize(serialize(tree))) == shape
assert serialize(from_level_order([1, 2, 3, None, None, 4, 5])) == "1,2,#,#,3,4,#,#,5,#,#"

A traversal without null markers is ambiguous: many trees share the same pre-order sequence. Markers (or two traversals, as in build_tree) remove the ambiguity.

Tries: prefix trees

A trie stores strings character by character; words sharing a prefix share a path. Lookups take O(length of the word), independent of how many words are stored.

class Trie:
    def __init__(self):
        self.root = {}
        self.END = "$"                       # marks the end of a complete word

    def insert(self, word):
        node = self.root
        for ch in word:
            node = node.setdefault(ch, {})
        node[self.END] = True

    def _walk(self, prefix):
        node = self.root
        for ch in prefix:
            if ch not in node:
                return None
            node = node[ch]
        return node

    def search(self, word):
        node = self._walk(word)
        return node is not None and self.END in node

    def starts_with(self, prefix):
        return self._walk(prefix) is not None


class WordDictionary(Trie):
    """Search where '.' matches any single letter."""

    def search(self, word):
        def match(node, i):
            if i == len(word):
                return self.END in node
            ch = word[i]
            if ch == ".":
                return any(match(child, i + 1) for key, child in node.items() if key != self.END)
            return ch in node and match(node[ch], i + 1)

        return match(self.root, 0)


trie = Trie()
trie.insert("apple")
assert trie.search("apple") and not trie.search("app") and trie.starts_with("app")
trie.insert("app")
assert trie.search("app")

wd = WordDictionary()
for w in ("bad", "dad", "mad"):
    wd.insert(w)
assert not wd.search("pad") and wd.search("bad") and wd.search(".ad") and wd.search("b..")
assert not wd.search("b.")

Nested dicts keep the code short. A node class with a children dict and an is_word flag is the more explicit alternative and is equally acceptable. The end marker matters: without it you cannot tell that “app” is a word rather than just a prefix of “apple”.

Complexity

Template	Time	Extra space
Any traversal, depth, invert, same tree	O(n)	O(h)
Subtree check	O(n·m) naive (n, m sizes of the trees)	O(h)
Diameter, balanced, max path sum, good nodes	O(n)	O(h)
Level order, right side view	O(n)	O(w), the maximum width
Lowest common ancestor	O(n)	O(h)
Build from traversals	O(n) with an index map	O(n)
Serialise, deserialise	O(n)	O(n)
Trie insert, search, prefix	O(L) for a word of length L	O(total characters stored)
Wildcard search	Up to O(alphabet^dots × L) in the worst case	O(L) recursion

Variations and common bugs

• Missing the None base case, or returning the wrong value for it (0 for depth, True for “same”, -inf for max).
• Confusing height in nodes with height in edges. Diameter is usually counted in edges.
• Computing height repeatedly inside a recursive check (O(n²)); return it with the answer instead.
• Forgetting to clamp negative branches to zero in max path sum, or initialising the best answer to 0 (wrong for all-negative trees).
• Not snapshotting len(queue) in level-order BFS, which mixes levels.
• Duplicate values break the index map in build_tree, and comparing nodes by value instead of identity breaks LCA.
• Recursion depth on skewed trees: use an iterative stack for very deep input.
• Variants: minimum depth (BFS stops at the first leaf), path sum (pass the remaining sum down), zigzag level order, symmetric tree, count complete tree nodes, vertical order traversal, flatten to a linked list.

Trees in data-engineering work

• Nested data. JSON documents and Parquet’s nested columns are trees. Flattening JSON into columns is a pre-order traversal that builds a dotted path on the way down.
• Hierarchies. Org charts, product categories and cost centres are trees stored as parent-child rows. “All reports under a manager” is a traversal; in SQL it is a recursive CTE, and the lowest common ancestor answers “which department contains both teams?”.
• Prefixes and paths. Object-store keys such as raw/events/date=2026-10-05/part-0.parquet form a trie of path segments. Prefix tries also power autocomplete and longest-prefix matching (IP routing tables).
• Query plans. A SQL plan or a Spark physical plan is a tree of operators; EXPLAIN output is a pre-order print of it.

def flatten_json(doc, prefix=""):
    """Pre-order traversal producing dotted column names."""
    flat = {}
    if isinstance(doc, dict) and doc:
        for key, value in doc.items():
            flat.update(flatten_json(value, f"{prefix}{key}."))
    elif isinstance(doc, list) and doc:
        for i, value in enumerate(doc):
            flat.update(flatten_json(value, f"{prefix}{i}."))
    else:
        flat[prefix[:-1]] = doc
    return flat


event = {"id": 7, "user": {"name": "Asha", "geo": {"country": "UK"}}, "tags": ["new", "mobile"]}
flat = flatten_json(event)
assert flat == {
    "id": 7,
    "user.name": "Asha",
    "user.geo.country": "UK",
    "tags.0": "new",
    "tags.1": "mobile",
}


def build_path_trie(keys):
    trie = {}
    for key in keys:
        node = trie
        for part in key.split("/"):
            node = node.setdefault(part, {})
    return trie


keys = ["raw/events/2026-10-04/a.parquet", "raw/events/2026-10-05/b.parquet", "raw/users/u.parquet"]
paths = build_path_trie(keys)
assert sorted(paths["raw"]["events"]) == ["2026-10-04", "2026-10-05"]
print(flat)

{'id': 7, 'user.name': 'Asha', 'user.geo.country': 'UK', 'tags.0': 'new', 'tags.1': 'mobile'}

Problems in this pattern

Recommended order, easy to hard:

1. Maximum Depth of Binary Tree (Easy): one plus the deeper child’s depth.
2. Invert Binary Tree (Easy): swap the children at every node.
3. Same Tree (Easy): both empty, or equal values and both pairs of subtrees the same.
4. Subtree of Another Tree (Easy): at each node, check Same Tree.
5. Balanced Binary Tree (Easy): return the height or −1 for unbalanced, in one pass.
6. Diameter of Binary Tree (Easy): at each node, left height plus right height; return the taller side.
7. Binary Tree Level Order Traversal (Medium): BFS, processing len(queue) nodes per level.
8. Binary Tree Right Side View (Medium): the last node of each BFS level.
9. Count Good Nodes in Binary Tree (Medium): pass the maximum on the path down.
10. Lowest Common Ancestor of Binary Tree (Medium): the first node where targets appear in both subtrees.
11. Construct Tree from Preorder and Inorder (Medium): pre-order gives the root; its in-order index splits the subtrees.
12. Implement Trie (Prefix Tree) (Medium): nested children maps plus an end-of-word marker.
13. Design Add and Search Words (Medium): trie search that branches over all children on a wildcard.
14. Binary Tree Maximum Path Sum (Hard): return the best one-sided gain, update the best two-sided path at each node.
15. Serialize and Deserialize Binary Tree (Hard): pre-order with null markers, rebuilt recursively from a token iterator.

Practice questions

What is the space complexity of recursive DFS on a binary tree?

O(h), where h is the tree’s height, for the call stack. That is O(log n) for a balanced tree and O(n) for a skewed one. In Python a skewed tree with thousands of nodes can exceed the recursion limit, so use an explicit stack for untrusted or very deep input.

When do you choose BFS over DFS for a tree problem?

Use BFS when the problem is about levels or the shortest distance from the root: level averages, right side view, minimum depth (stop at the first leaf). Use DFS when the answer is built from subtrees (heights, path sums, validation) or depends on the path from the root. Both are O(n) time; BFS uses O(width) memory and DFS uses O(height).

Why does the max path sum helper return a different value from the one it records as the best?

A path can bend at a node, using both children, but a path passed up to the parent can only continue down one side. So the helper records node + left + right as a candidate for the best answer and returns node + max(left, right) to the parent.

Why does serialising a tree need null markers?

Different trees can share the same pre-order or in-order sequence. For example, a root 1 with a left child 2, and a root 1 with a right child 2, both have pre-order 1, 2. Recording a marker for each missing child makes the encoding unique, so deserialisation can rebuild the exact shape.

What does a trie give you that a hash set of words does not?

Prefix queries. A set answers “is this exact word present?” in O(L), but “does any word start with this prefix?” or “list all words with this prefix” would require scanning every word. A trie answers prefix questions in O(prefix length) and can enumerate matches by walking the subtree. The cost is more memory per stored character.

Employees are stored as (employee_id, manager_id) rows. How do you list everyone under a given manager?

Build a dict from manager to direct reports, then traverse from the given manager with BFS or an explicit-stack DFS, collecting every node reached. Keep a visited set in case the data contains a cycle. In SQL, use a recursive CTE that starts from the manager and repeatedly joins reports to the previous level.

Key takeaways

• Most tree solutions are DFS (return values up, or pass state down) or level-by-level BFS; all are O(n).
• Space is O(height) for DFS and O(width) for BFS; skewed trees can exceed Python’s recursion limit.
• When the best answer may not pass through the root, return one value and track the best in a separate variable.
• Use null markers or two traversals to serialise or rebuild a tree unambiguously.
• Tries make prefix queries O(prefix length); an end-of-word marker distinguishes words from prefixes.
• Nested JSON, hierarchies, storage prefixes and query plans are trees in everyday data work.