Tree Interview Patterns

March 2026 · 10 min read

Most tree problems in interviews are variations of a handful of core patterns. Recognizing which pattern applies is half the battle. This post gives you the templates, the classic problems, and a cheat sheet for pattern recognition.

Pattern 1: Bottom-Up DFS (Post-Order)

When to use: When the answer for a node depends on answers from its children. Information flows upward.

Template:

Result solve(TreeNode* node) {
    if (!node) return BASE_CASE;
    auto leftResult  = solve(node->left);
    auto rightResult = solve(node->right);
    // Combine left + right + current node
    return combine(leftResult, rightResult, node->val);
}

Classic problems:

• Height / Maximum Depth: Return 1 + max(left, right)
• Diameter: Track left + right at each node while returning depth
• Balanced Tree Check: Return height if balanced, -1 if not. If either child returns -1, propagate -1 upward.
• Subtree Sum / Count: Return leftSum + rightSum + node->val
• Maximum Path Sum: Like diameter but with values. Track left + right + node as candidate, return max(left, right) + node upward.

Pattern 2: Top-Down DFS (Pre-Order)

When to use: When you carry context downward from parent to children. Information flows from root toward leaves.

Template:

void solve(TreeNode* node, Context ctx) {
    if (!node) return;
    // Process current node with context from parent
    process(node, ctx);
    solve(node->left, updateContext(ctx, node));
    solve(node->right, updateContext(ctx, node));
}

Classic problems:

• Root-to-Leaf Path Sum: Carry remainingSum downward. At a leaf, check if remaining == 0.
• All Root-to-Leaf Paths: Carry the current path as a vector. At a leaf, record it.
• Depth of Each Node: Pass depth + 1 to children.
• Validate BST: Pass (min, max) range downward. Each node must be within its parent's allowed range.

Pattern 3: BFS (Level-Order)

When to use: When the problem involves levels, layers, or finding the shortest path in an unweighted tree.

Template:

void levelOrder(TreeNode* root) {
    if (!root) return;
    std::queue<TreeNode*> q;
    q.push(root);
    while (!q.empty()) {
        int levelSize = q.size();  // nodes at current level
        for (int i = 0; i < levelSize; i++) {
            auto* node = q.front(); q.pop();
            process(node);
            if (node->left) q.push(node->left);
            if (node->right) q.push(node->right);
        }
    }
}

Classic problems:

• Level Averages: Sum values per level, divide by count.
• Zigzag Traversal: Alternate left-to-right and right-to-left at each level.
• Right/Left Side View: Last/first node at each level.
• Minimum Depth: BFS finds the first leaf, that's the minimum-depth leaf.
• Connect Nodes at Same Level: Link nodes within each BFS layer.

Pattern 4: Construct from Traversals

When to use: Reconstruct a tree from serialization or from traversal orders.

Key facts:

• Preorder + Inorder uniquely defines a binary tree. Preorder gives the root, inorder gives the left/right split.
• Postorder + Inorder also works (root is last in postorder).
• Preorder + Postorder is ambiguous for general trees (but unique for full binary trees).
• Sorted array → Balanced BST: Pick the middle element as root, recurse on left and right halves.

// Build tree from preorder + inorder
TreeNode* build(vector<int>& pre, int preStart, int preEnd,
                vector<int>& in, int inStart, int inEnd,
                unordered_map<int,int>& inMap) {
    if (preStart > preEnd) return nullptr;
    int rootVal = pre[preStart];
    auto* root = new TreeNode(rootVal);
    int inIdx = inMap[rootVal];     // root's position in inorder
    int leftSize = inIdx - inStart; // nodes in left subtree
    root->left  = build(pre, preStart+1, preStart+leftSize,
                        in, inStart, inIdx-1, inMap);
    root->right = build(pre, preStart+leftSize+1, preEnd,
                        in, inIdx+1, inEnd, inMap);
    return root;
}

Pattern 5: BST-Specific Tricks

When to use: When the problem gives you a BST (or you can exploit sorted order).

• In-order traversal = sorted order. Kth smallest? Do an in-order traversal and count to k.
• Validate BST: In-order should be strictly increasing. Or pass (min, max) bounds top-down.
• Two-sum in BST: Use a forward iterator (in-order) and a backward iterator (reverse in-order) like two pointers on a sorted array.
• LCA in BST: O(h) using the split-point property.
• Range queries: Skip branches that can't contain values in range.

How to Recognize the Pattern

Summary

• Most tree interview problems are one of 5 patterns: bottom-up DFS, top-down DFS, BFS, construction, or BST-specific.
• The key question to ask yourself: "Does information flow upward or downward?" Upward = post-order. Downward = pre-order.
• If the problem involves levels or shortest paths, use BFS.
• BST problems almost always exploit sorted in-order property.