Trees & BST

Trees are recursive structures — every subtree is itself a tree. This means almost every tree problem has an elegant recursive solution. The mental model: at each node, decide what information you need from children, compute it, and return what the parent needs. BSTs add the ordering invariant (left < root < right), making search O(log n) in balanced trees. Master the 4 traversals, LCA, and the recursive 'return value' pattern, and you cover 80% of tree interview problems. Understanding Trees A tree is a hierarchical data structure with a root node and children. Binary trees (max 2 children) are the most common in interviews. BSTs maintain the property: left < root < right. Why trees dominate interviews: They test recursive thinking Many real systems use trees (file systems, databases, DOM) Problems range from easy (traversal) to hard (balancing, serialization) Key traversals: Inorder (left, root, right): gives sorted order for BST Preorder (root, left, right): useful for serialization Postorder (left, right, root): useful for deletion, bottom-up calculation Level-order (BFS): uses a queue, processes level by level Key patterns: Recursive DFS: most tree problems are solved recursively Height/depth calculation: max(left, right) 1 LCA (Lowest Common Ancestor): fundamental for path problems BST validation: check if inorder traversal is sorted Trees & Binary Search Trees Trees are hierarchical structures. BSTs maintain the invariant: left < root < right, enabling O(log n) operations. Tree Traversals Lowest Common Ancestor Validate BST Key Problems #104 Max Depth, #226 Invert Tree, #235/236 LCA #98 Validate BST, #102 Level Order, #297 Serialize/Deserialize Interview Tip "For tree problems, I start by asking: can I solve this recursively? Most tree problems have elegant recursive solutions." Java Implementation: