Tree Problems for Coding Interviews

Tree Traversals

Inorder, preorder, postorder—recursive and iterative (using stack). Level-order (BFS with queue). Know when each is useful (e.g. inorder for BST gives sorted order).

Recursive Structure

Many tree problems: "do something for the root, then recurse for left and right, and combine." Examples: max depth, diameter, path sum.

Binary Search Tree

• Search, insert, delete.
• Validate BST: pass allowed range down the recursion.
• Kth smallest: inorder traversal with a counter.

Lowest Common Ancestor

• In BST: compare values with root to decide left or right.
• In general tree: recursive function returns node if found in subtree; LCA is where both sides return non-null.

Serialization and Construction

• Construct tree from inorder + preorder/postorder.
• Serialize/deserialize (e.g. level-order string).

Summary

Think in terms of "what do I need from the left and right subtrees?" Use Preplume(/) to practice tree problems by pattern.