Trees

What it is

This is a category, not one technique: problems where the input or output is a binary tree and the interesting work is choosing the right traversal order (preorder, inorder, postorder, or level-by-level) and the right shape of recursion — some problems want a value bubbled up from the leaves, others want state pushed down from the root, and reconstruction problems want you to run a traversal backwards. A file-system-style tree (directories and files) shows up too, tested the same way: pick the right walk and keep path/child bookkeeping in one place.

When it applies

• The problem statement gives you a tree and wants a value that summarizes it (a depth, a sum, an ancestor) or a rearranged view of it (levels, columns, a flattened list).
• You're given two traversal sequences, or a serialized string, and asked to rebuild the tree — this is really about the recursive structure a traversal encodes, so you invert it.
• You need to find nodes at a fixed distance or depth from another node, which usually means treating the tree as an undirected graph for that one search.
• It looks like a tree problem but is really about search order or comparison, not tree shape: choosing the smallest/largest value fast is closer to a heap pattern, and enforcing an ordering invariant across the whole tree is closer to the bst pattern.

Tells in the problem

• "Given the root of a binary tree, return..." paired with a per-node property.
• "Grouped by depth" or "grouped by column" — level order or a coordinate-keyed traversal.
• Two arrays like preorder and inorder describing the same tree, or a request to design serialize/deserialize.
• "Distance k from a given node" — signals you need parent pointers or an explicit map from child to parent before you can search upward.
• A directory/file tree with path-based operations (mkdir, ls, read) where paths must be parsed consistently once and reused.

The classic mistake

Reconstruction problems (preorder+inorder, or a serialized string) invite an O(n) linear scan through the array to find the root's position in inorder on every recursive call, which turns an O(n) rebuild into O(n²) on skewed trees. The fix is a single up-front index of value to position, or slicing by explicit boundaries instead of value search. Traversal problems have a parallel mistake: writing the level-order or vertical-order walk with implicit ordering assumptions (assuming children are visited left-to-right by construction) that break the moment two nodes tie on depth and column — the fix is to make the tie-break rule explicit in how you enqueue or sort, not rely on incidental iteration order.

Questions to start with

• Maximum Depth of Binary Tree — a plain recursive summary of the tree, the smallest version of "combine both children's results."
• Binary Tree Level Order Traversal — the level-by-level view, using a queue instead of recursion.
• Binary Tree Right Side View — level order with a twist: you keep only the last node seen at each depth.
• Construct Binary Tree from Preorder and Inorder Traversal — reconstruction, where an index map keeps the rebuild at O(n).
• Binary Tree Vertical Order Traversal — combines a coordinate system with an explicit tie-break rule for nodes that collide.
• All Nodes Distance K in Binary Tree — forces you to add parent links and search the tree as an undirected graph.
• Serialize and Deserialize Binary Tree — the hardest of the set: design your own encoding, then reconstruct from it without extra hints like array lengths.