Tree problems are the most common category in coding interviews, appearing in approximately 25% of questions at top tech companies. Understanding tree data structures and traversal patterns gives you the foundation to solve a wide range of problems. This guide covers binary trees, BSTs, tries, heaps, and the traversal patterns that appear most frequently in interviews.
Binary Tree Fundamentals
A binary tree is a hierarchical structure where each node has at most two children (left and right). Key terminology: root (top node), leaf (node with no children), depth (distance from root to node), height (distance from node to deepest leaf), and subtree (a node and all its descendants). Binary tree properties: a binary tree with N nodes has N-1 edges, the maximum number of nodes at depth d is 2^d, and the maximum number of nodes in a tree of height h is 2^(h+1) – 1. A complete binary tree fills every level except possibly the last, which is filled left to right. A perfect binary tree has every level completely filled. A balanced binary tree has the property that for every node, the height of the left and right subtrees differs by at most 1. Interview tip: always clarify whether the tree is a binary tree (any structure), a BST (ordered), or balanced. The algorithm and complexity change significantly.
Tree Traversal Patterns
Four traversal orders: (1) Pre-order (root, left, right) — visit the root first, then recursively traverse left subtree, then right subtree. Use for: serializing a tree (the output uniquely represents the tree structure), copying a tree. (2) In-order (left, root, right) — recursively traverse left subtree, visit root, traverse right subtree. For a BST, in-order traversal produces elements in sorted order. Use for: getting sorted output from a BST, finding the kth smallest element. (3) Post-order (left, right, root) — recursively traverse left subtree, right subtree, then visit root. Use for: deleting a tree (delete children before parent), calculating tree properties bottom-up (subtree size, subtree sum). (4) Level-order (BFS) — visit all nodes at depth 0, then depth 1, then depth 2. Use a queue. Use for: finding the minimum depth, printing level by level, connecting nodes at the same level. Implementation: recursive for pre/in/post-order (elegant, O(h) stack space). Iterative with an explicit stack when recursion depth is a concern. Queue-based for level-order.
Binary Search Tree (BST)
A BST maintains the invariant: for every node, all values in the left subtree are less, and all values in the right subtree are greater. This enables O(log N) search, insert, and delete in a balanced tree. Search: compare the target with the current node. If less, go left. If greater, go right. If equal, found. Insert: search for the position where the value belongs, insert as a new leaf. Delete: three cases — leaf (just remove), one child (replace with child), two children (replace with in-order successor or predecessor, then delete the successor/predecessor). BST pitfall: if elements are inserted in sorted order, the tree degenerates into a linked list with O(N) operations. Self-balancing BSTs (AVL, Red-Black) prevent this by maintaining balance after every insertion and deletion. Common BST interview problems: validate BST (check that in-order traversal is strictly increasing), find kth smallest (in-order traversal, count to k), find lowest common ancestor (if both targets are less than current, go left; if both greater, go right; otherwise current is the LCA).
Trie (Prefix Tree)
A trie stores strings efficiently by sharing common prefixes. Each node represents a character, and the path from root to a node represents a prefix. A boolean flag marks nodes that represent complete words. Operations: insert a word (traverse/create nodes for each character, mark the last node as a word end), search for a word (traverse nodes for each character, check word end flag), prefix search (traverse nodes for the prefix, then collect all words in the subtree). Time: O(L) for insert and search where L is the word length — independent of the number of stored words. Trie advantages: prefix search (find all words starting with “app”), autocomplete (find completions for a partial input), spell checking (find words within edit distance). Space: a naive trie uses a lot of memory (each node has 26 child pointers for lowercase English). Optimization: compressed trie (merge single-child chains into one node), hash map children (only store existing children). Common trie interview problems: implement trie (insert, search, startsWith), word search in a grid (DFS + trie for efficient prefix pruning), design autocomplete system (trie with frequency counts, return top-K suggestions).
Heap and Priority Queue
A heap is a complete binary tree where each parent is greater than or equal to its children (max-heap) or less than or equal (min-heap). The root is always the maximum (or minimum) element. Operations: insert O(log N) — add at the bottom, bubble up. Extract-max/min O(log N) — remove root, move last element to root, bubble down. Peek O(1) — return root without removing. Implementation: array-based (no pointer overhead). For node at index i: left child at 2i+1, right child at 2i+2, parent at (i-1)/2. Priority queue: an abstract data type backed by a heap. Used for: finding top-K elements, merge K sorted lists, Dijkstra shortest path, task scheduling by priority. Common heap interview problems: Kth largest element (min-heap of size K — maintain K largest elements, root is the Kth largest), merge K sorted lists (min-heap of K elements, one from each list, repeatedly extract-min and push the next element from that list), find median from data stream (max-heap for lower half, min-heap for upper half, balance sizes — median is the top of the larger heap or average of both tops).
Tree Problem-Solving Patterns
Pattern recognition for tree problems: (1) Top-down recursion (passing information from parent to child) — maximum depth, path sum (accumulate sum from root, check at leaf), validate BST (pass valid range down). (2) Bottom-up recursion (computing information from children to parent) — tree height, diameter (longest path = left_height + right_height at each node, track maximum), balanced tree check (compute height, return -1 if unbalanced). (3) Level-order (BFS) — minimum depth (first leaf found is the answer), right side view (last node at each level), zigzag traversal. (4) In-order for BST — kth smallest (count nodes during in-order), convert BST to sorted linked list, find closest value. (5) Serialize/deserialize — use pre-order with null markers for reconstruction. (6) Lowest Common Ancestor — for binary tree: recurse left and right, if both return non-null, current node is LCA. For BST: use the ordering property. Practice: solve 3-5 problems per pattern until recognition is automatic. Most tree problems reduce to choosing the right traversal order and deciding whether information flows top-down or bottom-up.
{“@context”:”https://schema.org”,”@type”:”FAQPage”,”mainEntity”:[{“@type”:”Question”,”name”:”What are the four tree traversal orders and when do you use each?”,”acceptedAnswer”:{“@type”:”Answer”,”text”:”Pre-order (root, left, right): visit root first. Use for serializing a tree structure and copying a tree. In-order (left, root, right): for a BST, produces elements in sorted order. Use for getting sorted output, finding kth smallest element. Post-order (left, right, root): visit root last. Use for deleting a tree (delete children before parent), computing bottom-up properties (subtree height, subtree sum). Level-order (BFS with queue): visit all nodes at each depth. Use for finding minimum depth, printing level by level, and connecting nodes at the same level. Implementation: recursive for pre/in/post-order (O(h) stack space). Queue-based for level-order. Choose the traversal order based on whether information flows top-down (pre-order) or bottom-up (post-order), or whether you need sorted output from a BST (in-order), or level-by-level processing (level-order).”}},{“@type”:”Question”,”name”:”How does a Trie work and what problems does it solve?”,”acceptedAnswer”:{“@type”:”Answer”,”text”:”A Trie (prefix tree) stores strings by sharing common prefixes. Each node represents a character; the path from root to a node represents a prefix. A boolean flag marks complete words. Operations: insert O(L), search O(L), prefix search O(L + K) where L is the word length and K is results. Advantages over hash tables: prefix search (find all words starting with app), autocomplete suggestions, and lexicographic ordering. Space optimization: compressed trie (merge single-child chains), hash map children (only store existing children). Common interview problems: implement Trie (insert, search, startsWith), word search in a grid (DFS + Trie for prefix pruning), and design autocomplete (Trie with frequency counts, return top-K). The key insight: Trie enables efficient prefix operations that hash tables cannot do, at the cost of more memory per entry.”}},{“@type”:”Question”,”name”:”What is a heap and how is it used as a priority queue?”,”acceptedAnswer”:{“@type”:”Answer”,”text”:”A heap is a complete binary tree where each parent is >= children (max-heap) or <= children (min-heap). The root is always the maximum (or minimum). Operations: insert O(log N) via bubble-up, extract-max/min O(log N) via bubble-down, peek O(1). Implementation: array-based (node at index i has children at 2i+1 and 2i+2). No pointer overhead. A priority queue is backed by a heap. Common interview problems: Kth largest element (maintain a min-heap of size K — root is the Kth largest), merge K sorted lists (min-heap of K elements, extract-min and push next from that list), median from data stream (max-heap for lower half, min-heap for upper half, balance sizes). Built-in: Java PriorityQueue, Python heapq, Go container/heap."}},{"@type":"Question","name":"What patterns help solve tree problems in coding interviews?","acceptedAnswer":{"@type":"Answer","text":"Six patterns cover most tree problems: (1) Top-down recursion — pass information from parent to child. Problems: maximum depth, path sum, validate BST (pass valid range). (2) Bottom-up recursion — compute from children to parent. Problems: tree height, diameter (left_height + right_height at each node), balanced check. (3) Level-order BFS — problems: minimum depth (first leaf), right side view (last node per level), zigzag traversal. (4) In-order for BST — problems: kth smallest, convert BST to sorted list, closest value. (5) Serialize/deserialize — use pre-order with null markers. (6) Lowest Common Ancestor — binary tree: recurse both sides, if both return non-null then current is LCA; BST: use ordering. Practice 3-5 problems per pattern. Most problems reduce to choosing the right traversal and deciding if information flows top-down or bottom-up."}}]}