Trees: Binary Trees, BSTs, and Traversals

Trees are everywhere in programming. File systems, HTML documents, database indexes, your compiler's parse tree. If you have ever clicked through nested folders or inspected a DOM element, you have used a tree without thinking about it.

In interviews, trees are one of the most tested data structures. They combine recursion, pointer manipulation, and algorithmic thinking in ways that arrays and linked lists do not. If you want to get comfortable with recursion, trees are the best place to practice.

What is a tree?

A tree is a collection of nodes connected by edges, with one special node called the root at the top. Each node can have zero or more children, and every node (except the root) has exactly one parent.

The key property: there are no cycles. You can never follow edges from a node and end up back where you started. This is what separates a tree from a general graph.

Terminology you need to know

Before we go further, here are the terms that show up constantly in tree problems:

• Root: the top node. It has no parent.
• Leaf: a node with no children. It sits at the bottom of the tree.
• Internal node: any node that has at least one child (not a leaf).
• Edge: the connection between a parent and a child.
• Depth: how many edges you need to travel from the root to reach a node. The root has depth 0.
• Height: the number of edges on the longest path from a node down to a leaf. A leaf has height 0.
• Subtree: any node plus all of its descendants. Every node is the root of its own subtree.

Binary trees

A binary tree is a tree where every node has at most two children, called the left child and the right child. This is the most common type of tree in interviews by a wide margin.

Most tree problems you will encounter use binary trees. The two-child limit keeps the structure simple enough to reason about while still being powerful enough to represent complex relationships.

A binary tree with n nodes has a height somewhere between log2(n) (perfectly balanced) and n - 1 (completely skewed, basically a linked list). Most algorithms run in O(h) time where h is the height, so keeping trees balanced matters a lot in practice.

The binary search tree (BST)

A binary search tree is a binary tree with one extra rule: for every node, all values in its left subtree are smaller, and all values in its right subtree are larger. This is the BST property, and it is what makes search, insert, and delete all O(log n) on a balanced tree.

The BST property is not just about direct children. Node 4 in the diagram above has 2 as its left child and 6 as its right child, which is correct. But 2 and 6 also need to satisfy constraints from their ancestors. The value 6 must be greater than 4 (its parent) but also less than 8 (the root). This ancestor constraint is why validating a BST is trickier than it looks at first.

Why BSTs matter

The BST property gives you something arrays cannot: O(log n) search, insert, and delete on the same data structure. Arrays give you O(1) access by index but O(n) insert/delete. Linked lists give you O(1) insert/delete but O(n) search. BSTs split the difference.

In practice, self-balancing trees like AVL trees and red-black trees guarantee the O(log n) bound by automatically rebalancing after insertions and deletions. You rarely implement these from scratch in interviews, but understanding why balance matters helps you reason about time complexity.

Tree traversals

Traversal means visiting every node in the tree exactly once. There are four standard traversals, and they come up constantly in problems. The first three are depth-first (DFS), and the last one is breadth-first (BFS).

Inorder (Left, Root, Right)

Visit the left subtree, then the current node, then the right subtree. On a BST, this produces values in sorted order. If you ever need to get BST values in order, inorder traversal is the answer.

def inorder(node):
    if not node:
        return
    inorder(node.left)
    print(node.val)   # process the node
    inorder(node.right)

Preorder (Root, Left, Right)

Visit the current node first, then the left subtree, then the right subtree. Preorder is useful for serializing a tree (converting it to a flat representation) or copying a tree, because you process each node before its children.

def preorder(node):
    if not node:
        return
    print(node.val)   # process the node
    preorder(node.left)
    preorder(node.right)

Postorder (Left, Right, Root)

Visit the left subtree, then the right subtree, then the current node. Postorder processes children before the parent, which makes it perfect for problems where you need the result from children to compute the parent's answer. Calculating tree height, for example, is naturally postorder.

def postorder(node):
    if not node:
        return
    postorder(node.left)
    postorder(node.right)
    print(node.val)   # process the node

BFS (Level-order)

Visit all nodes at depth 0, then depth 1, then depth 2, and so on. BFS uses a queue instead of recursion.

from collections import deque

def level_order(root):
    if not root:
        return
    queue = deque([root])
    while queue:
        node = queue.popleft()
        print(node.val)
        if node.left:
            queue.append(node.left)
        if node.right:
            queue.append(node.right)

BFS is the go-to when you need to process the tree level by level, find the shortest path to a node, or work with the tree's "shape" rather than its recursive structure.

Recursion on trees

Trees and recursion are natural partners. Every subtree is itself a tree, so you can solve most tree problems by solving the problem on the left subtree, solving it on the right subtree, and combining the results. This is the recursive structure of trees.

The general template looks like this:

def solve(node):
    # Base case: empty tree
    if not node:
        return base_value

    # Recurse on subtrees
    left_result = solve(node.left)
    right_result = solve(node.right)

    # Combine results
    return combine(left_result, right_result, node.val)

Different problems change what base_value is, what combine does, and whether you process the node before or after the recursive calls. But the skeleton stays the same.

For example, maximum depth is:

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

And counting all nodes is:

def count_nodes(node):
    if not node:
        return 0
    return count_nodes(node.left) + count_nodes(node.right) + 1

Same pattern, different combine function. Once you see this, tree problems become much less intimidating.

The two types of tree recursion

Most tree problems fall into one of two categories. Knowing which type you are dealing with helps you structure your solution.

1. Top-down (passing information down)

You pass information from parent to child via function parameters. The classic example is validating a BST: you pass a valid range (min, max) down, and each node checks whether its value falls within that range.

def is_valid_bst(node, lo=float('-inf'), hi=float('inf')):
    if not node:
        return True
    if node.val <= lo or node.val >= hi:
        return False
    return (is_valid_bst(node.left, lo, node.val) and
            is_valid_bst(node.right, node.val, hi))

2. Bottom-up (returning information up)

You compute answers from the leaves upward, combining child results to get the parent's answer. Maximum depth is the classic bottom-up problem: leaf nodes return 0, and each parent takes the max of its children plus 1.

Some problems use both directions at once. The "diameter of binary tree" problem, for instance, needs bottom-up height information but tracks the global maximum diameter as a side effect.

Common mistakes with trees

A few pitfalls that come up again and again:

1. Forgetting the base case. If node is None, return immediately. Every tree recursive function needs this. Without it, you will hit an AttributeError on the first leaf node's child.

2. Only checking direct children for BST validation. As mentioned above, you need to check the entire valid range from ancestors, not just the immediate parent. Use a (lo, hi) range that narrows as you recurse.

3. Confusing height and depth. Height is measured from a node down to the farthest leaf. Depth is measured from the root down to the node. They go in opposite directions.

4. Not handling unbalanced trees. If your algorithm assumes the tree is balanced, it might work on test cases but fail on a tree that is basically a linked list. Always consider the worst case.

Problems you should practice

These are the essential tree problems for interviews. They cover the core patterns: recursion, traversal, BST properties, and tree construction.

• Maximum Depth of Binary Tree: the simplest tree recursion problem. If you can solve this, you understand the bottom-up pattern.
• Invert Binary Tree: swap left and right children recursively. Tests whether you understand tree modification.
• Symmetric Tree: check if a tree is a mirror of itself. A great exercise in writing two-pointer-style recursion on trees.
• Validate BST: the classic top-down range-passing problem. Tests whether you understand the BST property deeply.
• Lowest Common Ancestor: find the shared ancestor of two nodes. Combines recursion with careful case analysis.
• Serialize/Deserialize Binary Tree: convert a tree to a string and back. Tests traversal mechanics and reconstruction logic.

Each of these problems uses a different variation of the recursive template. Once you can solve all six from scratch, you will be comfortable with nearly any tree problem an interviewer throws at you.

Reading about trees is not enough

Understanding the binary tree data structure and BST interview patterns conceptually is the easy part. The hard part is producing the recursive code from scratch when you are under pressure and the clock is ticking.

Tree recursion is especially tricky because each problem looks slightly different. The base case changes, the combine step changes, the direction of information flow changes. If you have only read through solutions, you might recognize the pattern but struggle to write it. That is the gap between recognition and recall.

Spaced repetition closes that gap. You practice each building block (the traversal skeleton, the range-passing technique, the bottom-up combine) at increasing intervals. Each time, you type the code from scratch. After a few repetitions, the patterns are permanent. When you see a tree traversal problem in an interview, you do not have to think about the structure. It is already in your fingers.

CodeBricks breaks tree problems into their reusable pieces and drills them individually. The scheduling adapts to how well you remember each one. Short sessions, spread over time, building real fluency instead of cramming.

Related posts

• Maximum Depth of Binary Tree - The simplest tree recursion problem and a great starting point
• Validate BST - Deep dive into BST validation with the range-passing technique
• Lowest Common Ancestor - A classic tree problem combining recursion with case analysis
• Invert Binary Tree - Tree modification through recursion

---

New to algorithms? Start with our visual What is an Algorithm? guide, or learn Big O Notation to understand tree time complexity.