Binary Trees
On this page
Folder structures, org charts, expression parsers and decision rules are all hierarchies, and a flat list can't answer questions like "how deep is this?" or "what do these two have in common?" without a lot of bookkeeping. Trees are the most common data structure in coding interviews after arrays and hash maps, and almost every tree question is solved with the same small idea: ask each child for an answer, then combine.
How it works
Nodes with up to two children

A binary tree is made of nodes, each holding a value and pointers to at most two children, left and right.
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
The words you'll use in every tree problem:
- Root: the top node. Leaf: a node with no children.
- Subtree: any node together with everything below it. Every subtree is itself a binary tree, which is why recursion fits so well.
- Depth of a node: edges from the root. Height of a tree: the number of levels on its longest root-to-leaf path. A tree with n nodes has height between about log₂ n (balanced) and n (a chain).
Visiting every node: DFS and BFS

Depth-first search (DFS) goes all the way down one branch before backing up. It comes in three orders, depending on when you handle the node itself:
- Preorder (node, left, right): copying or serializing a tree, because you see a parent before its children.
- Inorder (left, node, right): on a binary search tree, this visits values in sorted order.
- Postorder (left, right, node): when a node's answer depends on its children's answers (height, sums, diameters).
Breadth-first search (BFS), or level order, visits row by row using a queue. Use it when the question mentions levels, the left or right view, or the nearest something.
The core idea: answer from the children

Most tree problems are solved by writing one recursive function and trusting it on the children:
- Base case: what is the answer for an empty tree (
None)? - Recursive case: get the answers for
leftandright, then combine them with the current node.
Maximum depth is the simplest example: depth(node) = 1 + max(depth(left), depth(right)), and depth(None) = 0.
Operations and costs
| Operation | Cost |
|---|---|
| Visit every node (any DFS order or BFS) | O(n) time |
| Recursion stack for DFS | O(h) space, where h is the height |
| BFS queue | O(w) space, where w is the widest level (up to about n/2) |
| Find a value in a plain binary tree | O(n): no ordering, so you may check every node |
For a balanced tree h is O(log n); for a skewed tree (a chain) h is O(n), so recursive DFS can use O(n) stack.
When to reach for it
- The input is a tree: almost always DFS with a recursive helper, or BFS if the problem talks about levels.
- You need the answer for a node from its children's answers: postorder DFS that returns values.
- You need information from the path above a node (current sum, allowed range, depth): DFS that passes values down as parameters.
- You need both: return one thing up and track a global best on the side (diameter, maximum path sum).
Example
Maximum depth with DFS, and level order with BFS:
from collections import deque
def max_depth(root):
if root is None:
return 0
return 1 + max(max_depth(root.left), max_depth(root.right))
def level_order(root):
if not root:
return []
out, q = [], deque([root])
while q:
level = []
for _ in range(len(q)): # exactly the nodes of this level
node = q.popleft()
level.append(node.val)
if node.left:
q.append(node.left)
if node.right:
q.append(node.right)
out.append(level)
return out
The depth function in the other three languages:
int maxDepth(TreeNode root) {
if (root == null) return 0;
return 1 + Math.max(maxDepth(root.left), maxDepth(root.right));
}
int maxDepth(TreeNode* root) {
if (!root) return 0;
return 1 + max(maxDepth(root->left), maxDepth(root->right));
}
func maxDepth(root *TreeNode) int {
if root == nil {
return 0
}
return 1 + max(maxDepth(root.Left), maxDepth(root.Right))
}
(Go 1.21 and later has a built-in max; on older versions write a two-line helper.)
Time: O(n) for both. Space: O(h) for the recursion, O(w) for the BFS queue. For the tree in the pictures, depth is 3 and level order is [[1], [2, 3], [4, 5, 6]].
Common mistakes
- Missing the base case. Every recursive tree function must handle
Nonefirst. - Returning the wrong thing. Decide what the function returns for a subtree (a height? a sum? a boolean?) and keep it consistent.
- Mixing up "return up" and "best overall". In diameter or path-sum problems the value you return to the parent is not the answer; keep the answer in a separate variable.
- Only checking a node against its children. Some properties (like "valid BST") depend on all ancestors, so pass a range down.
- Forgetting the level size in BFS. Take
len(q)before the inner loop, or levels blur together. - Stack overflow on deep trees. If the tree can be a long chain (10⁵ nodes), mention an iterative version with an explicit stack.
Say this in the interview
- "I'll write a recursive helper that returns the height of a subtree; each node combines its children's heights."
- "This visits each node once, so O(n) time and O(h) space for the recursion, which is O(log n) if balanced and O(n) in the worst case."
- "The question is about levels, so I'll use BFS with a queue and process one level per outer loop."
Used in
- Patterns: Tree DFS, Tree BFS
- Problems: Maximum Depth of Binary Tree, Invert Binary Tree, Diameter of Binary Tree, Lowest Common Ancestor of a Binary Tree, Binary Tree Level Order Traversal, Binary Tree Maximum Path Sum, Serialize and Deserialize Binary Tree
- Data structures: Binary Search Trees, Heaps, Tries, Stacks and Queues