Binary Trees are hierarchical data structures that form the foundation of many advanced algorithms and real-world applications. Unlike linear structures (arrays, linked lists), trees represent non-linear relationships, making them ideal for representing hierarchies, organizing data efficiently, and solving complex algorithmic problems.
This comprehensive guide explores binary tree theory, traversal techniques, and demonstrates essential patterns through 15+ LeetCode problems.
Understanding Binary Trees: Core Concepts
What is a Binary Tree?
A Binary Tree is a non-linear data structure where each node has at most two children, referred to as the left child and right child. Trees are a subcategory of directed graphs, with edges pointing from parent to child.
# Binary Tree Node Definition
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
Essential Tree Terminology
Basic Terms:
Node: Individual element containing a value
Root: Topmost node (no parent)
Parent: Node with children
Child: Node descended from another node
Leaf: Node with no children
Branch: Edge connecting parent to child
Subtree: Tree formed by a node and its descendants
Tree Properties:
Height (Depth): Longest path from root to leaf
Width (Breadth): Maximum number of nodes at any level
Level: Distance from root (root is level 0)
Types of Binary Trees
Complete Binary Tree:
- All levels fully filled except possibly the last
- Last level filled from left to right
- Efficient for heap implementations
Full Binary Tree:
- Every node has either 0 or 2 children
- No node has only one child
Perfect Binary Tree:
- All internal nodes have two children
- All leaves at same level
- Total nodes = 2^(h+1) - 1
LeetCode Representation:
Binary trees in LeetCode often appear as arrays with null values representing missing nodes:
[3, 9, 20, null, null, 15, 7]
3
/ \
9 20
/ \
15 7
Tree Traversal: DFS vs BFS
Understanding traversal is crucial for solving tree problems. Two main approaches exist: Depth-First Search (DFS) and Breadth-First Search (BFS).
DFS Traversal (Stack/Recursion)
DFS explores as deep as possible before backtracking. Three ordering patterns exist:
1. Preorder (Node → Left → Right)
- Process root first
- Use case: Copying tree, creating prefix expressions
2. Inorder (Left → Node → Right)
- Process left subtree, then root, then right
Special property: Returns sorted order for BST
3. Postorder (Left → Right → Node)
- Process children before parent
- Use case: Deleting tree, calculating tree properties
Time Complexity: O(n) - visit each node once
Space Complexity: O(h) - recursion stack, worst case O(n)
BFS Traversal (Queue)
BFS explores level by level (also called Level Order Traversal).
Characteristics:
- Uses queue data structure
- Processes nodes level by level
- Great for finding shortest path, min depth
Time Complexity: O(n)
Space Complexity: O(w) - queue size, worst case O(n)
Essential Binary Tree Patterns
Pattern 1: Invert Binary Tree
Problem: Given the root of a binary tree, invert the tree and return its root (mirror image).
Approach: Recursively swap left and right children for every node.
Time: O(n) | Space: O(h)
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def invertTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
# Base case: empty tree
if not root:
return root
# Swap children
root.left, root.right = root.right, root.left
# Recursively invert subtrees
self.invertTree(root.left)
self.invertTree(root.right)
return root
Key Insight: Classic recursion problem. Each node performs the same operation: swap children and recurse.
Pattern 2: Merge Two Binary Trees
Problem: Merge two binary trees by summing overlapping nodes.
Approach: Recursively merge trees. If both nodes exist, sum values. Otherwise, use the existing node.
Time: O(min(n, m)) | Space: O(h)
class Solution:
def mergeTrees(self, root1: Optional[TreeNode], root2: Optional[TreeNode]) -> Optional[TreeNode]:
# If one tree is empty, return the other
if not root1:
return root2
if not root2:
return root1
# Both exist: sum values
root1.val += root2.val
# Recursively merge subtrees
root1.left = self.mergeTrees(root1.left, root2.left)
root1.right = self.mergeTrees(root1.right, root2.right)
return root1
Key Insight: Handle base cases first (null nodes), then perform operation and recurse.
Pattern 3: Maximum Depth of Binary Tree
Problem: Find the maximum depth (height) of a binary tree.
Approach: Recursively calculate depth of left and right subtrees, return max + 1.
Time: O(n) | Space: O(h)
class Solution:
def maxDepth(self, root: Optional[TreeNode]) -> int:
if not root:
return 0
# Get height of subtrees
l_height = self.maxDepth(root.left)
r_height = self.maxDepth(root.right)
# Current height = 1 + max of subtrees
return 1 + max(l_height, r_height)
Key Insight: Tree height problems naturally fit recursive solutions. Think in terms of subtree properties.
Pattern 4: Minimum Depth (BFS Approach)
Problem: Find the minimum depth (shortest path to a leaf).
Approach: Use BFS to find the first leaf node encountered.
Why BFS? BFS finishes early when finding the first leaf, while DFS must explore all paths.
Time: O(n) | Space: O(w)
from collections import deque
class Solution:
def minDepth(self, root: Optional[TreeNode]) -> int:
if not root:
return 0
# Queue stores (node, depth) pairs
q = deque([(root, 1)])
while q:
node, depth = q.popleft()
# Found leaf node - return immediately
if not node.left and not node.right:
return depth
# Add children with incremented depth
if node.left:
q.append((node.left, depth + 1))
if node.right:
q.append((node.right, depth + 1))
Key Insight: Choose BFS for "minimum/shortest" problems where early termination is beneficial.
Pattern 5: Same Tree (BFS)
Problem: Check if two binary trees are structurally identical with same values.
Approach: Use BFS to compare nodes level by level.
Time: O(n) | Space: O(w)
from collections import deque
class Solution:
def isSameTree(self, p: Optional[TreeNode], q: Optional[TreeNode]) -> bool:
# Both empty = same
if not p and not q:
return True
# Queue stores pairs of nodes to compare
dq = deque([(p, q)])
while dq:
p_node, q_node = dq.popleft()
# Both null = continue
if not p_node and not q_node:
continue
# One null or values differ = not same
if not p_node or not q_node or p_node.val != q_node.val:
return False
# Add children pairs
dq.append((p_node.left, q_node.left))
dq.append((p_node.right, q_node.right))
return True
Key Insight: Process pairs of nodes simultaneously using a queue.
Pattern 6: Symmetric Tree (DFS & BFS)
Problem: Check if a binary tree is a mirror of itself (symmetric around center).
Approach: Compare left and right subtrees as mirror images.
DFS Solution:
class Solution:
def isSymmetric(self, root: Optional[TreeNode]) -> bool:
if not root:
return True
def dfs(left, right):
# Both null = symmetric
if not left and not right:
return True
# One null = not symmetric
if not left or not right:
return False
# Check: values equal AND subtrees mirror each other
return (left.val == right.val and
dfs(left.left, right.right) and # Outside pair
dfs(left.right, right.left)) # Inside pair
return dfs(root.left, root.right)
BFS Solution:
from collections import deque
class Solution:
def isSymmetric(self, root: Optional[TreeNode]) -> bool:
if not root:
return True
q = deque([(root.left, root.right)])
while q:
left, right = q.popleft()
if not left and not right:
continue
if not left or not right or left.val != right.val:
return False
# Mirror pairs: outside and inside
q.append((left.left, right.right))
q.append((left.right, right.left))
return True
Key Insight: Symmetry requires comparing mirror positions: left.left ↔ right.right, left.right ↔ right.left.
Pattern 7: Balanced Binary Tree
Problem: Check if a binary tree is height-balanced (left and right subtree heights differ by at most 1 for every node).
Approach: Calculate heights while checking balance condition. Use flag to short-circuit.
Time: O(n) | Space: O(h)
class Solution:
def isBalanced(self, root: Optional[TreeNode]) -> bool:
if not root:
return True
# Flag to track balance status
res = [True]
def dfs(r):
if not r:
return 0
# Get left height
l_height = dfs(r.left)
# Short-circuit if already unbalanced
if not res[0]:
return 0
# Get right height
r_height = dfs(r.right)
# Check balance condition
if abs(l_height - r_height) > 1:
res[0] = False
return 0
return 1 + max(l_height, r_height)
dfs(root)
return res[0]
Key Insight: Use mutable container (list) to maintain state across recursive calls.
Pattern 8: Binary Tree Paths
Problem: Return all root-to-leaf paths.
Approach: DFS with path tracking. Backtrack after exploring each path.
DFS Solution:
class Solution:
def binaryTreePaths(self, root: Optional[TreeNode]) -> List[str]:
res = []
def dfs(root, path):
if not root:
return
# Add current node to path
path.append(str(root.val))
# Leaf node: save path
if not root.left and not root.right:
res.append("->".join(path))
else:
# Explore children
dfs(root.left, path)
dfs(root.right, path)
# Backtrack: remove current node
path.pop()
dfs(root, [])
return res
BFS Solution:
from collections import deque
class Solution:
def binaryTreePaths(self, root: Optional[TreeNode]) -> List[str]:
res = []
q = deque([(root, str(root.val))])
while q:
node, path = q.popleft()
# Leaf node: save path
if not node.left and not node.right:
res.append(path)
# Add children with updated paths
if node.left:
q.append((node.left, path + "->" + str(node.left.val)))
if node.right:
q.append((node.right, path + "->" + str(node.right.val)))
return res
Key Insight: DFS with backtracking vs BFS with path strings—both valid, choose based on space/time tradeoffs.
Pattern 9: Diameter of Binary Tree
Problem: Find the length of the longest path between any two nodes (path may not pass through root).
Approach: At each node, calculate diameter passing through that node (left_height + right_height). Track maximum.
Time: O(n) | Space: O(h)
class Solution:
def diameterOfBinaryTree(self, root: Optional[TreeNode]) -> int:
longest_diameter = [0]
def dfs(root):
if not root:
return 0
# Get subtree heights
l_height = dfs(root.left)
r_height = dfs(root.right)
# Diameter through this node
diameter = l_height + r_height
longest_diameter[0] = max(longest_diameter[0], diameter)
# Return height for parent
return 1 + max(l_height, r_height)
dfs(root)
return longest_diameter[0]
Key Insight: Diameter at a node = sum of left and right subtree heights. Return height, track diameter separately.
Pattern 10: Path Sum
Problem: Check if the tree has a root-to-leaf path that sums to targetSum.
Approach: Subtract current value from target, recurse. Leaf node should have target = 0.
Time: O(n) | Space: O(h)
class Solution:
def hasPathSum(self, root: Optional[TreeNode], targetSum: int) -> bool:
if not root:
return False
# Leaf node: check if target reached
if not root.left and not root.right:
return targetSum - root.val == 0
# Subtract current value and recurse
targetSum -= root.val
return (self.hasPathSum(root.left, targetSum) or
self.hasPathSum(root.right, targetSum))
Key Insight: Pass remaining sum down the tree. Leaf nodes check for exact match.
Pattern 11: Path Sum II (All Paths)
Problem: Find all root-to-leaf paths that sum to targetSum.
Approach: DFS with path tracking and backtracking.
Time: O(n) | Space: O(h)
class Solution:
def pathSum(self, root: Optional[TreeNode], targetSum: int) -> List[List[int]]:
if not root:
return []
res = []
def dfs(root, path):
if not root:
return
path.append(root.val)
# Leaf node: check sum
if not root.left and not root.right and sum(path) == targetSum:
res.append(path[:]) # Copy path
else:
dfs(root.left, path)
dfs(root.right, path)
# Backtrack
path.pop()
dfs(root, [])
return res
Key Insight: Use path[:] to create a copy when saving results. Backtracking reuses the same list.
Pattern 12: Count Good Nodes
Problem: Count nodes that are greater than or equal to all nodes in the path from root.
Approach: Track maximum value seen so far in the path. Increment count if current >= max.
Time: O(n) | Space: O(h)
class Solution:
def goodNodes(self, root: TreeNode) -> int:
def dfs(root, max_so_far):
if not root:
return 0
# Check if current node is "good"
good = 1 if root.val >= max_so_far else 0
# Update max for children
max_so_far = max(root.val, max_so_far)
# Count good nodes in subtrees
left = dfs(root.left, max_so_far)
right = dfs(root.right, max_so_far)
return good + left + right
return dfs(root, root.val)
Key Insight: Pass down state (max value) and accumulate results (count) upward.
Binary Search Tree (BST) Patterns
BST Properties
Definition: For every node:
- All nodes in left subtree < node value
- All nodes in right subtree > node value
Key Property: Inorder traversal of BST produces sorted sequence
Time Complexity (Balanced): O(log n) for search, insert, delete
Pattern 13: Validate BST
Problem: Check if a binary tree is a valid BST.
Approach: Track valid range (min, max) for each node. Left child must be in (min, node.val), right child in (node.val, max).
Time: O(n) | Space: O(h)
class Solution:
def isValidBST(self, root: Optional[TreeNode]) -> bool:
def isValid(root, minn, maxx):
if not root:
return True
# Check range violation
if root.val <= minn or root.val >= maxx:
return False
# Left: (minn, root.val), Right: (root.val, maxx)
return (isValid(root.left, minn, root.val) and
isValid(root.right, root.val, maxx))
return isValid(root, float('-inf'), float('inf'))
Key Insight: Use range bounds, not just parent value. A node must satisfy constraints from all ancestors.
Pattern 14: Kth Smallest Element in BST
Problem: Find the kth smallest element in a BST.
Approach: Inorder traversal produces sorted order. Stop at kth element.
Time: O(k) best, O(n) worst | Space: O(h)
class Solution:
def kthSmallest(self, root: Optional[TreeNode], k: int) -> int:
count = [k]
res = [0]
def dfs(root):
if not root:
return
# Inorder: left, node, right
dfs(root.left)
# Process current node
if count[0] == 1:
res[0] = root.val
count[0] -= 1
# Only continue if not found yet
if count[0] > 0:
dfs(root.right)
dfs(root)
return res[0]
Key Insight: Inorder traversal of BST visits nodes in sorted order. Count down to find kth.
Pattern 15: Lowest Common Ancestor in BST
Problem: Find the lowest common ancestor of two nodes in a BST.
Approach: Use BST property to navigate. If both nodes < current, go left. If both > current, go right. Otherwise, current is LCA.
Time: O(h) | Space: O(h)
class Solution:
def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
lca = [root]
def dfs(root):
if not root:
return
lca[0] = root
# Found one of the nodes
if root == p or root == q:
return
# Both in left subtree
if root.val > p.val and root.val > q.val:
dfs(root.left)
# Both in right subtree
elif root.val < p.val and root.val < q.val:
dfs(root.right)
# Split: current node is LCA
else:
return
dfs(root)
return lca[0]
Key Insight: LCA is the first node where paths to p and q diverge. Use BST property for efficient navigation.
Pattern 16: Subtree of Another Tree
Problem: Check if subRoot is a subtree of root.
Approach: For each node in root, check if subtree matches subRoot.
Time: O(n × m) | Space: O(h)
class Solution:
def isSubtree(self, root: Optional[TreeNode], subRoot: Optional[TreeNode]) -> bool:
def isSameTree(s, t):
if not s and not t:
return True
if not s or not t or s.val != t.val:
return False
return isSameTree(s.left, t.left) and isSameTree(s.right, t.right)
if not subRoot:
return True
if not root:
return False
# Check current node or recurse
if isSameTree(root, subRoot):
return True
return (self.isSubtree(root.left, subRoot) or
self.isSubtree(root.right, subRoot))
Key Insight: Combine two patterns: tree comparison and tree traversal.
Common Tree Techniques & Patterns
1. Recursion Pattern
Base case: null node
Recursive case: process node, recurse on children
Return: aggregated result from subtrees
2. DFS with State
- Pass down: max/min values, path, depth
- Accumulate up: count, sum, height
- Use mutable containers for flags
3. BFS Level Order
- Use queue with (node, metadata)
- Process entire level before next
- Great for "minimum" problems
4. Backtracking
- Add to path → Explore → Remove from path
- Essential for path enumeration
- Use
path[:]for copying
5. BST Navigation
- Use BST property for directed search
- O(log n) for balanced trees
- Inorder traversal = sorted order
Time & Space Complexity Summary
| Operation | Time | Space |
|---|---|---|
| DFS Traversal | O(n) | O(h) recursion stack |
| BFS Traversal | O(n) | O(w) queue size |
| Height Calculation | O(n) | O(h) |
| Path Finding | O(n) | O(h) |
| BST Search (balanced) | O(log n) | O(h) |
| BST Search (worst) | O(n) | O(n) |
Note:
- h = height (best: log n, worst: n)
- w = width (worst: n/2 for perfect tree)
- n = number of nodes
Practice Strategy
Foundation (Easy)
- Invert Binary Tree
- Max Depth
- Same Tree
- Merge Trees
- Path Sum
Core Patterns (Easy-Medium)
- Symmetric Tree
- Min Depth
- Balanced Tree
- Binary Tree Paths
- Diameter
Advanced (Medium)
- Path Sum II
- Lowest Common Ancestor
- Validate BST
- Kth Smallest in BST
- Count Good Nodes
- Subtree
Tips
Draw trees: Visualize recursion flow
Master base cases: null nodes, leaf nodes
Choose traversal wisely: DFS for paths, BFS for levels
BST advantage: Use ordering property
Practice both: Iterative and recursive solutions
Key Takeaways
Trees are recursive - Each subtree is itself a tree
Master DFS & BFS - Choose based on problem requirements
Inorder BST = Sorted - Powerful property for BST problems
Pass state down, aggregate up - Common recursion pattern
Backtracking for paths - Add, explore, remove
Height vs Depth - Height measured from bottom, depth from top
Space complexity - O(h) for DFS, O(w) for BFS
Binary trees are fundamental to computer science, appearing in databases (B-trees), compilers (syntax trees), file systems, and countless algorithms. Mastering tree traversal and recursion opens doors to solving complex hierarchical problems efficiently.
Continue building your DSA foundation. Trees connect many concepts: recursion, graphs, dynamic programming. Practice regularly and patterns will become intuitive.