Trees Pattern

The Trees pattern involves traversing hierarchical, non-cyclic node structures where each node has a single parent and zero or more children, using depth-first search or breadth-first search.

Recognition Signals

You should consider this pattern if you see any of the following cues in the problem description:

• The data structure is explicitly defined as a binary tree, binary search tree (BST), or n-ary tree.
• The problem asks about paths, ancestors, depth, height, or matching subtrees.
• You need to perform lookups or insertions in sorted order in sub-linear time.

How It Works

Instead of flat iteration (which works on linear lists), tree algorithms use recursion (Depth-First Search) or queues (Breadth-First Search) to navigate paths:

• DFS (Pre/In/Post-Order): Recursively visit the current node, the left subtree, and the right subtree. The order of operations defines the traversal type.
• BFS (Level-Order): Use a queue to process nodes level by level, draining the queue size snapshot at each level step.

For example, to calculate the maximum depth of a binary tree:

1. If the node is null, return 0.
2. Recursively find the depth of the left subtree: leftDepth = maxDepth(node.left).
3. Recursively find the depth of the right subtree: rightDepth = maxDepth(node.right).
4. Return 1 + max(leftDepth, rightDepth).

Complexity, With Caveats

• Time Complexity: O(n) for traversals, as you must visit all nodes. O(h) for search operations in a valid BST (where h is the tree height). In the worst case (skewed tree), h is equal to n; for a balanced tree, h is O(log n).
• Space Complexity: O(h) auxiliary space representing the recursion stack depth. In the worst case (skewed tree), space is O(n).

Minimal Code Template

import java.util.LinkedList;
import java.util.Queue;

public class TreesTemplate {
    public static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode(int val) { this.val = val; }
    }

    // Depth-First Search (DFS)
    public void traverseDFS(TreeNode root) {
        if (root == null) return;
        // Pre-order processing
        traverseDFS(root.left);
        // In-order processing
        traverseDFS(root.right);
        // Post-order processing
    }

    // Breadth-First Search (BFS / Level Order)
    public void traverseBFS(TreeNode root) {
        if (root == null) return;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);

        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                TreeNode curr = queue.poll();
                if (curr.left != null) queue.offer(curr.left);
                if (curr.right != null) queue.offer(curr.right);
            }
        }
    }
}

from collections import deque


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


# Depth-First Search (DFS)
def traverse_dfs(root: TreeNode) -> None:
    if not root:
        return
    # Pre-order processing
    traverse_dfs(root.left)
    # In-order processing
    traverse_dfs(root.right)
    # Post-order processing


# Breadth-First Search (BFS / Level Order)
def traverse_bfs(root: TreeNode) -> None:
    if not root:
        return
    queue = deque([root])

    while queue:
        size = len(queue)
        for _ in range(size):
            curr = queue.popleft()
            if curr.left:
                queue.append(curr.left)
            if curr.right:
                queue.append(curr.right)

#include <queue>

class TreesTemplate {
public:
    struct TreeNode {
        int val;
        TreeNode* left;
        TreeNode* right;
        TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    };

    // Depth-First Search (DFS)
    void traverseDFS(TreeNode* root) {
        if (!root) return;
        // Pre-order processing
        traverseDFS(root->left);
        // In-order processing
        traverseDFS(root->right);
        // Post-order processing
    }

    // Breadth-First Search (BFS / Level Order)
    void traverseBFS(TreeNode* root) {
        if (!root) return;
        std::queue<TreeNode*> q;
        q.push(root);

        while (!q.empty()) {
            int size = q.size();
            for (int i = 0; i < size; i++) {
                TreeNode* curr = q.front();
                q.pop();
                if (curr->left) q.push(curr->left);
                if (curr->right) q.push(curr->right);
            }
        }
    }
};

Where This Pattern Falls Short

• Recursive stack limits: For exceptionally deep trees (e.g. height > 10⁴), recursive implementations can trigger stack overflow errors. You must write an iterative traversal using an explicit stack or queue instead.
• Graph connectivity: If the node connections can form cycles (meaning nodes can link back to their ancestors), tree algorithms will loop indefinitely. You must use Graph traversal with visited sets instead.

Related Patterns, Compared

• Graphs: choose this instead when the node paths can contain cycles or are not connected as a single rooted hierarchy.
• Tries: choose this specialized sub-pattern when you need to store and match string prefix segments character-by-character.

Frequently Asked Questions

What is the difference between Binary Search Tree (BST) and Binary Tree? A Binary Tree is any tree where each node has at most 2 children. A Binary Search Tree enforces the ordering rule: for any node, all left descendants are strictly smaller, and all right descendants are strictly larger.

What is the difference between DFS and BFS? DFS uses a stack (or recursion) to go as deep as possible down one branch before backtracking. BFS uses a queue to visit all neighbors at the current level before moving to the next level.

What does this pattern test in interviews? It tests your ability to think recursively, structure base cases correctly, and coordinate pointers without memory leaks.