What is a Binary Tree?
A binary-tree node points to at most two children, left and right. The useful property is that each child begins another complete binary tree.
You need references, recursion, and a clear null base case. The short version is: ask each child for the information it owns, then use those answers at the current node.
The Core Idea: Ask the Children
In LC 104: Maximum Depth, the root is 3. Its left subtree has depth 1, while the subtree rooted at 20 has depth 2.
What is the root's answer? Take the larger child depth and add one for the root, giving depth 3. The same rule works at every node.
It is like a manager asking each team lead for the size of their deepest reporting chain. The manager keeps the larger report and adds their own level.
How a Postorder Answer Moves Up
The Rule You Keep True
Each recursive call must return the correct summary for the entire subtree rooted at its input node. The parent should not need to inspect that subtree again.
Information can travel in either direction:
- Return upward when a parent needs child results, as in depth or diameter.
- Pass downward when children need ancestor state, as in BST bounds.
- Change links after child calls when reshaping a tree, as in inversion.
- Return a found node upward when locating a common ancestor.
LC 543: Diameter of Binary Tree is the one that usually trips us up. The longest path may pass through any node, not just the root. One postorder call should return height upward while also updating the best left-height plus right-height seen anywhere.
Picking the Right Shape
From Rule to Code
- Define what one recursive call receives and returns.
- Handle null before reading child fields.
- Recurse into the children in the order required by the problem.
- Combine child results or pass updated state downward.
- Return one complete answer for the current subtree.
Every node is processed once in these traversals, giving O(n) time and O(h) recursion space for tree height h.
When to use it
- •The input is a root node whose children form smaller trees.
- •The answer depends on depth, height, paths, ancestors, or subtree properties.
- •Left and right subtree answers must be combined at each node.
- •A binary-search-tree ordering rule can remove part of the search.
How to identify it
- •The function receives `root` rather than an array or string.
- •Words such as subtree, leaf, depth, height, ancestor, or balanced appear.
- •The prompt asks to invert, validate, serialize, or otherwise reshape a tree.
- •A node must return information upward or receive bounds or path state from above.
Key insights
- →Each child is the root of a complete smaller tree, so the same function can solve it.
- →Postorder is the natural choice when a node needs both child answers first.
- →Preorder is useful when state must be passed from a parent to its children.
- →BST validation needs ancestor bounds, not only comparisons with the direct parent.
- →Recursion stack space follows tree height, which can be `n` for a chain-shaped tree.
Common mistakes
- 01Skipping the null base case.
- 02Mixing height measured in nodes with height measured in edges.
- 03Assuming every binary tree follows BST ordering.
- 04Checking a BST node only against its parent instead of all inherited bounds.
- 05Recomputing subtree height inside another traversal and turning **O(n)** work into **O(n²)**.