Introduction
A tree is a hierarchical data structure consisting of nodes connected by edges. Each node contains a value and references to its children (and sometimes its parent). The topmost node is called the root, and nodes with no children are called leaves.
Unlike arrays or linked lists which are linear, trees branch out, making them perfect for representing hierarchical relationships like file systems, HTML DOM, or family trees.
Think of a tree like a real tree turned upside down. The root node is at the top, and it branches downward. An n-ary tree means each node can have at most n children. Most commonly, you will work with 2-ary trees (binary trees).
Important Base Cases:
- if not root: return - When the node is empty, stop
- if not root.left and not root.right: - This node is a leaf node
- if not root.left or not root.right: - This node is a leaf OR has one null child
TreeNode Definition
Standard binary tree node structure.
Visual Example:
5 Level 0 (Root)
/ \
3 7 Level 1
/ \ \
1 4 9 Level 2
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val # int, string, whatever value
self.left = left # recursively defined, TreeNode type
self.right = right # recursively defined, TreeNode typeThe Three Traversals
The key to mastering tree problems is understanding the three fundamental traversal patterns:
- Preorder (Root → Left → Right)
- Inorder (Left → Root → Right)
- Postorder (Left → Right → Root)
Imagine moving around the tree counter-clockwise, starting from root 5:
- Preorder: 5, 3, 1, 4, 7, 9 - Dot at the left side of each node
- Inorder: 1, 3, 4, 5, 7, 9 - Dot at the bottom of each node
- Postorder: 1, 4, 3, 9, 7, 5 - Dot at the right of each node
Preorder processes top-down. Postorder processes bottom-up from leaves. Understanding when to use each is crucial!
Preorder Traversal
Process root before children. Good for building/modifying trees (top-down).
def preorder(node):
if not node: return
result.append(node.val) # Process root FIRST
preorder(node.left)
preorder(node.right)Inorder Traversal
Process root between children. KEY INSIGHT: Inorder traversal of a BST gives nodes in sorted order!
def inorder(node):
if not node: return
inorder(node.left)
result.append(node.val) # Process root in MIDDLE
inorder(node.right)Postorder Traversal
Process root after children. Good for bottom-up computation. Most basic DFS problems use postorder.
def postorder(node):
if not node: return
postorder(node.left)
postorder(node.right)
result.append(node.val) # Process root LASTBasic Traversal Problems
Fundamental problems demonstrating tree traversal patterns.
01Binary Tree Inorder TraversalEasy
Given the root of a binary tree, return the inorder traversal of its nodes' values.
def inorderTraversal(self, root: TreeNode) -> List[int]:
result = []
def dfs(node):
if not node:
return
dfs(node.left) # Process left
result.append(node.val) # Process root
dfs(node.right) # Process right
dfs(root)
return resultO(n)O(h)h is the height of the tree. Similarly, see preorder (Q144) and postorder (Q145) traversals.
02Invert Binary TreeEasy
Given the root of a binary tree, invert the tree (swap every left node with its corresponding right node).
# Preorder solution
def invertTree(self, root: TreeNode) -> TreeNode:
if not root:
return None
# Swap children FIRST (preorder)
root.left, root.right = root.right, root.left
# Recursively invert subtrees
self.invertTree(root.left)
self.invertTree(root.right)
return root
# Postorder solution
def invertTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
if not root: return root
root.left, root.right = self.invertTree(root.right), self.invertTree(root.left)
return rootO(n)O(h)We don't just swap values - the ENTIRE subtree is swapped. This can be written in preorder, inorder, or postorder!
03Same TreeEasy
Given the roots of two binary trees p and q, determine if they are the same tree. Two binary trees are the same if they are structurally identical and have the same values.
def isSameTree(self, p: TreeNode, q: TreeNode) -> bool:
# Base cases: if either tree is empty
if not p and not q:
return True
if not p or not q:
return False
# Check current nodes and recursively check subtrees
return (p.val == q.val and
self.isSameTree(p.left, q.left) and
self.isSameTree(p.right, q.right))O(min(n1, n2))O(min(h1, h2))This introduces comparing two trees simultaneously. Two empty trees are the same, but an empty and non-empty tree are different. This is postorder - we need results from subtrees first.
04Symmetric TreeEasy
Given the root of a binary tree, check if it is a mirror of itself (symmetric around its center).
def isSymmetric(self, root: TreeNode) -> bool:
def mirror(left: TreeNode, right: TreeNode) -> bool:
if not left and not right:
return True
if not left or not right:
return False
return (left.val == right.val and
mirror(left.left, right.right) and
mirror(left.right, right.left))
return not root or mirror(root.left, root.right)
# Alternative: compare tree with itself
def isSymmetric(self, root: Optional[TreeNode]) -> bool:
def dfs(root1, root2):
if not root1 or not root2:
return not root1 and not root2
return (root1.val == root2.val and
dfs(root1.right, root2.left) and
dfs(root1.left, root2.right))
return dfs(root, root)O(n)O(h)Instead of comparing a node with itself, we compare corresponding nodes from left and right subtrees. The left subtree of tree1 must mirror the right subtree of tree2.
Depth & Path Problems
Problems involving tree depth, height, and path calculations.
01Maximum Depth of Binary TreeEasy
Find the height of a binary tree (the number of nodes along the longest path from root to leaf).
def maxDepth(self, root: TreeNode) -> int:
if not root:
return 0
return 1 + max(self.maxDepth(root.left),
self.maxDepth(root.right))O(n)O(h)Postorder. The max depth at a node is the max of left and right depths + 1 for the current node.
02Minimum Depth of Binary TreeEasy
Find the minimum depth of a binary tree (shortest path from root to leaf).
def minDepth(self, root: TreeNode) -> int:
if not root:
return 0
if not root.left:
return 1 + self.minDepth(root.right)
if not root.right:
return 1 + self.minDepth(root.left)
return 1 + min(self.minDepth(root.left),
self.minDepth(root.right))
# Alternative with inf trick
def minDepth(self, root: Optional[TreeNode]) -> int:
def helper(root):
if not root: return float('inf')
if not root.left and not root.right: return 1
return 1 + min(helper(root.left), helper(root.right))
return helper(root) if root else 0O(n)O(h)Notice the difference from maxDepth - we handle empty subtrees specially. Without this, min(x, 0) would always be 0 instead of x. Compare with max(x, 0) = x.
03Path SumEasy
Given the root of a binary tree and a target sum, determine if there exists a root-to-leaf path where the sum of all node values equals the target.
def hasPathSum(self, root: Optional[TreeNode], targetSum: int) -> bool:
if not root: return False
if not root.left and not root.right:
return targetSum == root.val
return (self.hasPathSum(root.left, targetSum - root.val) or
self.hasPathSum(root.right, targetSum - root.val))O(n)O(h)Track cumulative value as we traverse. We subtract from target rather than adding up - this simplifies the leaf check!
04Sum Root to Leaf NumbersMedium
Given a binary tree containing digits from 0 to 9 only, where each root-to-leaf path represents a number (e.g., 1 -> 2 -> 3 = 123), return the total sum of all root-to-leaf numbers.
def sumNumbers(self, root: Optional[TreeNode]) -> int:
res = 0
def subtree(root, path):
nonlocal res
if not root: return
v = 10 * path + root.val
if not root.left and not root.right:
res += v
return
subtree(root.left, v)
subtree(root.right, v)
subtree(root, 0)
return resO(n)O(h)Preorder traversal. Update the path number using 10 * path + root.val. Example: 123 = ((1) * 10 + 2) * 10 + 3. Use global state (res) updated during traversal.
05Binary Tree Maximum Path SumHard
Find the maximum path sum between any two nodes in the tree. The path can be "V-shaped" - it doesn't have to be a straight line down.
def maxPathSum(self, root: Optional[TreeNode]) -> int:
res = float('-inf')
# Returns max NON-EMPTY path that passes through/starts at root
def dfs(root):
if not root:
return 0
nonlocal res
left_max = dfs(root.left)
right_max = dfs(root.right)
# Update global res with V-shaped path through this node
res = max(res, max(0, left_max) + root.val + max(0, right_max))
# Return best single-direction path including this node
return max(root.val, root.val + left_max, root.val + right_max)
dfs(root)
return resO(n)O(h)The path can be "V-shaped". If dfs(root) returns the max straight-chain path including root, we update res with: best_left + root.val + best_right. Every node could be the top of the optimal V. Use max(0, path) since paths can be negative.
Binary Search Trees
A Binary Search Tree (BST) has the property: for any node, all nodes in the left subtree are < node.val, and all nodes in the right subtree are > node.val.
KEY PROPERTY: An inorder traversal of a BST gives nodes in sorted order.
01Validate Binary Search TreeMedium
Determine if a binary tree is a valid binary search tree (BST).
def isValidBST(self, root: Optional[TreeNode]) -> bool:
def isValid(root, lower_bound, upper_bound):
if not root: return True
return (lower_bound < root.val < upper_bound and
isValid(root.left, lower_bound, root.val) and
isValid(root.right, root.val, upper_bound))
return isValid(root, float('-inf'), float('inf'))O(n)O(h)Pass down constraints that get tighter as we go down. The invariant: isValid(node, min, max) is true iff node is a valid BST AND all values are within (min, max).
02Lowest Common Ancestor of a Binary Search TreeMedium
Given a BST, find the lowest common ancestor (LCA) of two given nodes.
def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
def lca(root):
if p.val < root.val and q.val < root.val:
return lca(root.left)
if p.val > root.val and q.val > root.val:
return lca(root.right)
# p,q are split in opposite subtrees (or one is root)
return root
return lca(root)O(h)O(h)BST properties enable O(h) instead of O(n). Three cases: LCA is on left, on right, or is current node. With balanced BSTs, h = O(log n).
Level Order / BFS
Problems requiring level-based information use BFS with a queue.
01Binary Tree Level Order TraversalMedium
Return the level-order traversal of a binary tree's values.
def levelOrder(self, root: TreeNode) -> List[List[int]]:
if not root:
return []
res = []
q = deque([root])
while q:
level = []
for _ in range(len(q)):
node = q.popleft()
level.append(node.val)
if node.left:
q.append(node.left)
if node.right:
q.append(node.right)
res.append(level)
return resO(n)O(w)BFS on a tree. w is the maximum width (max nodes at any level). Process all nodes at current level before moving to next level.
Lowest Common Ancestor
LCA is important theoretically and in real applications. The LCA of nodes p and q is the lowest (deepest) node that has both p and q as descendants.
01Lowest Common Ancestor of a Binary TreeMedium
Given a binary tree, find the lowest common ancestor (LCA) of two given nodes p and q.
def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
res = None
def dfs(root): # Returns count of p,q in subtree (0, 1, or 2)
if not root: return 0
nonlocal res
l = dfs(root.left)
r = dfs(root.right)
curr = root == p or root == q
if res is None and l + r + curr == 2:
res = root
return l + r + curr
dfs(root)
return resO(n)O(h)Postorder traversal. The FIRST time l + r + curr == 2 (with res still None) is the LCA. Subsequent ancestors will also have sum == 2 but res is already set.
02Lowest Common Ancestor of a Binary Tree IVMedium
Given a binary tree and a list of target nodes, return the lowest common ancestor of all target nodes. All targets exist in the tree.
def lowestCommonAncestor(self, root: 'TreeNode', nodes: 'List[TreeNode]') -> 'TreeNode':
targets = set(nodes)
res = None
def dfs(node):
if not node:
return 0
nonlocal res
left = dfs(node.left)
right = dfs(node.right)
curr = node in targets
if res is None and left + right + curr == len(targets):
res = node
return left + right + curr
dfs(root)
return resO(n)O(h + k)This is the same postorder LCA count idea as the two-node version, generalized from count == 2 to count == len(nodes).
03Lowest Common Ancestor of a Binary Tree IIIMedium
Given two nodes p and q with parent pointers, return their LCA.
def lowestCommonAncestor(self, p: 'Node', q: 'Node') -> 'Node':
og_p, og_q = p, q
while p != q:
p = p.parent if p else og_q
q = q.parent if q else og_p
return pO(h)O(1)Classic trick: p travels x to LCA then z to root. q travels y to LCA then z to root. If p starts at og_p and q starts at og_q, both travel x+y+z steps to meet at LCA!
04Smallest Common RegionMedium
Given region hierarchy lists (first region contains all others in its list), find the smallest region containing both region1 and region2.
def findSmallestRegion(self, regions: List[List[str]], region1: str, region2: str) -> str:
# Build parent pointers
parent = defaultdict(str)
for region in regions:
for i in range(1, len(region)):
parent[region[i]] = region[0]
# Do LCA with parent pointers
og_p, og_q = region1, region2
p, q = og_p, og_q
while p != q:
p = parent[p] if p else og_q
q = parent[q] if q else og_p
return pO(n)O(n)The key insight is recognizing this is a tree LCA problem! Model the region hierarchy as a tree, build parent pointers, and run LCA.
Advanced Problems
More complex tree problems combining multiple techniques.
01Count Nodes Equal to Average of SubtreeMedium
Count nodes whose value equals the integer average of all values in their subtree.
def averageOfSubtree(self, root: Optional[TreeNode]) -> int:
res = 0
def subtree_info(node):
if not node:
return 0, 0
nonlocal res
left_sum, left_count = subtree_info(node.left)
right_sum, right_count = subtree_info(node.right)
total = node.val + left_sum + right_sum
count = 1 + left_count + right_count
if total // count == node.val:
res += 1
return total, count
subtree_info(root)
return resO(n)O(h)This is the source's fundamental subtree pattern: return multiple values, here (sum, count), from each postorder call instead of traversing the same subtree repeatedly.
02Distribute Coins in Binary TreeMedium
Given a binary tree with n nodes where each node has some coins (total = n), return the minimum moves to make every node have exactly one coin. One move = transfer one coin between adjacent nodes.
def distributeCoins(self, root: Optional[TreeNode]) -> int:
res = 0
def size_sum(root):
if not root: return 0, 0
left_size, left_sum = size_sum(root.left)
right_size, right_sum = size_sum(root.right)
nonlocal res
# Coins that must flow across this edge = |size - sum|
res += abs(left_size - left_sum) + abs(right_size - right_sum)
return (left_size + 1 + right_size,
left_sum + root.val + right_sum)
size_sum(root)
return resO(n)O(h)Key insight: we reason about EDGES, not nodes. For each edge, we compute exactly how many coins must flow across it: |subtree_size - subtree_coin_sum|. We don't care where coins come from!
03Construct Binary Tree from Preorder and Inorder TraversalMedium
Given preorder and inorder traversals of a tree, construct the binary tree.
def buildTree(self, preorder: List[int], inorder: List[int]) -> TreeNode:
# Map value -> index in inorder
inorder_idx = {v: i for i, v in enumerate(inorder)}
preorder_index = 0
def build(left, right):
nonlocal preorder_index
if left > right:
return None
# Root is next element in preorder
root_val = preorder[preorder_index]
root = TreeNode(root_val)
preorder_index += 1
# Split inorder array at root
root.left = build(left, inorder_idx[root_val] - 1)
root.right = build(inorder_idx[root_val] + 1, right)
return root
return build(0, len(preorder) - 1)O(n)O(n)Preorder = [root, L, R]. Inorder = [L, root, R]. The root is the first preorder element. Use inorder to find where left/right subtrees split. Build left subtree first (matches preorder).
04Construct Binary Tree from Preorder and Postorder TraversalMedium
Given preorder and postorder traversals, construct the binary tree. If multiple valid trees exist, return any.
def constructFromPrePost(self, preorder: List[int], postorder: List[int]) -> TreeNode:
post_idx = {v: i for i, v in enumerate(postorder)}
pre_index = 0
def build(post_left, post_right):
nonlocal pre_index
if post_left > post_right:
return None
root = TreeNode(preorder[pre_index])
pre_index += 1
if post_left == post_right:
return root
# Next preorder element is left child's root
left_root = preorder[pre_index]
left_end = post_idx[left_root]
root.left = build(post_left, left_end)
root.right = build(left_end + 1, post_right - 1)
return root
return build(0, len(postorder) - 1)O(n)O(n)Preorder = [root, L, R]. Postorder = [L, R, root]. The second preorder element is left subtree's root. Find it in postorder to split left/right subtrees.
05Lowest Common Ancestor of a Binary Tree IIMedium
Find LCA of two nodes p and q. Return null if either node doesn't exist in the tree.
def lowestCommonAncestor(self, root: TreeNode, p: TreeNode, q: TreeNode) -> TreeNode:
self.found_p = False
self.found_q = False
def dfs(node):
if not node:
return None
left = dfs(node.left)
right = dfs(node.right)
if node == p:
self.found_p = True
return node
if node == q:
self.found_q = True
return node
if left and right:
return node
return left or right
result = dfs(root)
return result if self.found_p and self.found_q else NoneO(n)O(h)Same as basic LCA but must verify both nodes exist. Track found_p/found_q flags. Only return result if both were found during traversal.
Problem-Solving Framework
1. Choose the right traversal:
- Need sorted order? → Inorder
- Build/modify tree? → Preorder
- Bottom-up computation? → Postorder
- Level-based info? → BFS
2. Identify useful information to pass:
- Down the tree: constraints, targets
- Up the tree: heights, sums, counts
- Globally: maximum values, results
3. Handle special cases:
- Empty tree
- Single node
- Unbalanced trees
- Invalid input
Remember: Most tree problems can be solved by selecting the right traversal pattern and carefully managing state as you traverse!