Overview
A binary tree is a set of nodes where each node has at most two children. Trees model hierarchies — file systems, organisation charts, parsed expressions — and they are the most common interview topic after arrays. Nearly every tree problem is solved by visiting each node once, so the real question is in what order and carrying what information.
Think of each recursive call as asking a subtree a question. Top-down solutions pass information down (the depth so far, the allowed range). Bottom-up solutions ask each child for an answer and combine them (the height of a subtree, whether it is balanced). Breadth-first traversal with a queue handles anything phrased in terms of levels.
Key concepts
Tick a concept once you can explain it in your own words without notes.
Complexity cheat sheet
| Operation | Cost |
|---|---|
| Any traversal | O(n) time |
| Recursion stack | O(h): O(log n) balanced, O(n) skewed |
| BFS queue | O(w) where w is the maximum width |
Patterns to recognise
Return from children
Use it for: Max depth, diameter, balanced tree, max path sum.
Compute left and right results, combine, and update a global best if needed.
Carry state down
Use it for: Path sum, good nodes, sum root-to-leaf numbers.
Add the current node to the state before recursing into children.
Level order
Use it for: Right side view, average of levels, zigzag traversal.
BFS, processing len(queue) nodes per level.
Code template
from collections import deque
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val, self.left, self.right = val, left, right
def max_depth(root):
if not root:
return 0
return 1 + max(max_depth(root.left), max_depth(root.right))
def level_order(root):
if not root:
return []
levels, queue = [], deque([root])
while queue:
level = []
for _ in range(len(queue)):
node = queue.popleft()
level.append(node.val)
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
levels.append(level)
return levels
struct TreeNode {
int val;
TreeNode *left, *right;
TreeNode(int v = 0) : val(v), left(nullptr), right(nullptr) {}
};
int maxDepth(TreeNode* root) {
if (!root) return 0;
return 1 + max(maxDepth(root->left), maxDepth(root->right));
}
vector<vector<int>> levelOrder(TreeNode* root) {
vector<vector<int>> levels;
if (!root) return levels;
queue<TreeNode*> q;
q.push(root);
while (!q.empty()) {
vector<int> level;
for (int i = (int)q.size(); i > 0; --i) {
TreeNode* node = q.front(); q.pop();
level.push_back(node->val);
if (node->left) q.push(node->left);
if (node->right) q.push(node->right);
}
levels.push_back(level);
}
return levels;
}
Common mistakes
- Forgetting the null case — every recursive tree function needs it first.
- Confusing depth and height, or counting edges vs nodes; read the definition in the problem.
- A global "best" variable must be reset between test cases.
- Deep, skewed trees can overflow the recursion stack — iterate with an explicit stack if n is large.
Quick check
Three questions on Binary Trees. Get all three right to earn +15 XP.
-
Inorder traversal visits nodes in which order?
Left subtree first, then the node, then the right subtree.
-
A recursive DFS on a tree with n nodes and height h uses how much stack space?
The stack holds one frame per level on the current root-to-node path.
-
Level-order traversal of a binary tree is implemented with:
It is breadth-first search: process a level, enqueue its children.
Challenges
Ordered from easiest to hardest. Solve them on LeetCode, then tick them off here. Know every concept and solve 3 to clear the level.
- Maximum Depth of Binary TreeLeetCode Easy +20
- Invert Binary TreeLeetCode Easy +20
- Same TreeLeetCode Easy +20
- Diameter of Binary TreeLeetCode Easy +20
- Binary Tree Level Order TraversalLeetCode Medium +40
- Binary Tree Right Side ViewLeetCode Medium +40
- Lowest Common Ancestor of a Binary TreeLeetCode Medium +40
- Construct Binary Tree from Preorder and Inorder TraversalLeetCode Medium +40
- Binary Tree Maximum Path SumLeetCode Hard +70
- Serialize and Deserialize Binary TreeLeetCode Hard +70
Stuck on Binary Trees?Ask Orbi for a hint, a fresh explanation or a review of your code.
Ask the tutor