Top Tree Interview Questions 2026

Trees are the second most common data structure in coding interviews after arrays. DFS traversal patterns and BST properties cover the majority of tree questions.

DFS Traversal Patterns

Three orderings: preorder (root, left, right), inorder (left, root, right), postorder (left, right, root). Inorder of a BST produces a sorted sequence. Preorder serializes the tree structure. Postorder is used in bottom-up computations like subtree size.

Recursive DFS is natural but risks stack overflow on skewed trees (O(n) call stack). Iterative DFS using an explicit stack avoids this. Know both implementations. BFS (level-order) uses a queue and visits nodes level by level.

BST Operations

BST invariant: left subtree values < node value < right subtree values (for all nodes, not just children). Search/insert/delete: O(h) where h is height. Balanced BST: h = O(log n). Skewed BST: h = O(n).

BST to sorted list: inorder traversal. Validate BST: pass min/max bounds down the recursion, not just compare with immediate children. Floor and ceiling: find the largest value <= target (floor) or smallest >= target (ceiling).

Lowest Common Ancestor

LCA for binary tree: traverse both paths to root and find the last common node. Or: DFS returning the LCA when both target nodes are found in subtrees. Time O(n), space O(h).

LCA for BST exploits BST property: if both targets are less than current node, go left; both greater, go right; otherwise, current node is the LCA. Time O(h), space O(1) for iterative.

Tree Construction

Build binary tree from preorder + inorder: first element of preorder is root; find root in inorder to split left/right subtrees. Recurse. Build from postorder + inorder: last element of postorder is root.

Serialize/deserialize: preorder with null markers. Serialize: preorder traversal, write 'null' for null nodes. Deserialize: process a queue of tokens, consuming one per recursive call. Both are O(n) time and space.

Browse Real Tree Questions

See actual tree problems asked at Google, Meta, and Amazon.

Browse Tree Questions