3. Base Template (Python Tree Traversals)
Below is a Python template for common tree traversals, using a simple TreeNode class.
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
# Pre-order Traversal (Root -> Left -> Right)
def preorder_traversal(root: TreeNode):
if root is None: return []
result = [root.val]
result.extend(preorder_traversal(root.left))
result.extend(preorder_traversal(root.right))
return result
# In-order Traversal (Left -> Root -> Right)
def inorder_traversal(root: TreeNode):
if root is None: return []
result = []
result.extend(inorder_traversal(root.left))
result.append(root.val)
result.extend(inorder_traversal(root.right))
return result
# Post-order Traversal (Left -> Right -> Root)
def postorder_traversal(root: TreeNode):
if root is None: return []
result = []
result.extend(postorder_traversal(root.left))
result.extend(postorder_traversal(root.right))
result.append(root.val)
return result
# Level-order Traversal (BFS)
from collections import deque
def level_order_traversal(root: TreeNode):
if root is None: return []
result = []
queue = deque([root])
while queue:
node = queue.popleft()
result.append(node.val)
if node.left: queue.append(node.left)
if node.right: queue.append(node.right)
return resultpreorder(1): result = [1]- Call
preorder(2): result = [2], returns [2] -
result.extend([2])-> result = [1, 2] - Call
preorder(3): result = [3], returns [3] -
result.extend([3])-> result = [1, 2, 3] - Return [1, 2, 3]
4. Variants & Patterns (Tree Traversals)
DFS Traversal Variants
DFS with Path Tracking (Root-to-Leaf Paths Sum)
Modified Template: Add parameters for running sum and current path list in DFS. Recurse, on leaf check sum. Backtrack by removing node from path.
Example Problem: LeetCode 113. Path Sum II – Find all root-to-leaf paths where sum equals target.
- Root 1 (path [1], sum 1) -> L: 2 (path [1,2], sum 3) -> L: 4 (path [1,2,4], sum 7). Leaf, sum≠10. Backtrack.
- Node 2 -> R: 7 (path [1,2,7], sum 10). Leaf, sum==10. Record [1,2,7]. Backtrack.
- Root 1 -> R: 4 (path [1,4], sum 5) -> L: 5 (path [1,4,5], sum 10). Leaf, sum==10. Record [1,4,5]. Backtrack.
- Result: [[1,2,7],[1,4,5]].
def pathSum(root, target):
res = []
def dfs(node, cur_path, cur_sum):
if not node: return
cur_path.append(node.val)
cur_sum += node.val
if not node.left and not node.right and cur_sum == target:
res.append(list(cur_path))
else:
dfs(node.left, cur_path, cur_sum)
dfs(node.right, cur_path, cur_sum)
cur_path.pop() # Backtrack
dfs(root, [], 0)
return resDFS for Tree Transformation (Flatten Tree to List)
Modified Template: Use global pointer (or return value) for previously processed node. Traverse right subtree, then left (reverse pre-order). Rewire current node: node.right = prev, node.left = None. Update prev = node.
Example Problem: LeetCode 114. Flatten Binary Tree to Linked List – Flatten in-place to pre-order "linked list".
// C++ example
TreeNode* prev_node = nullptr; // Use a class member or global-like static
void flatten(TreeNode* root) {
if (!root) return;
flatten(root->right);
flatten(root->left);
root->right = prev_node;
root->left = NULL;
prev_node = root;
}DFS Post-order for Lowest Common Ancestor (LCA)
Modified Template: DFS returns node pointer (target or LCA candidate). If node is p or q, return it. If left child returns p and right returns q (or vice-versa), current node is LCA. Else, propagate non-null child result.
Example Problem: LeetCode 236. Lowest Common Ancestor of a Binary Tree.
// Java example
TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
if (root == null || root == p || root == q) return root;
TreeNode left = lowestCommonAncestor(root.left, p, q);
TreeNode right = lowestCommonAncestor(root.right, p, q);
if (left != null && right != null) return root; // LCA found
return (left != null) ? left : right;
}Divide & Conquer DFS (Tree Construction)
Modified Template: Pick root from one traversal (e.g., pre-order[0]). Find root in inorder to split. Recursively build left/right subtrees from corresponding traversal segments. Use indices to avoid array copies.
Example Problem: LeetCode 105. Construct Tree from Preorder and Inorder Traversal.
def buildTree(preorder, inorder):
inorder_idx_map = {val: i for i, val in enumerate(inorder)}
preorder_idx = 0 # Global or nonlocal if Python 2/early 3
def helper(in_left, in_right):
nonlocal preorder_idx
if in_left > in_right: return None
root_val = preorder[preorder_idx]
root = TreeNode(root_val)
preorder_idx += 1
inorder_root_idx = inorder_idx_map[root_val]
root.left = helper(in_left, inorder_root_idx - 1)
root.right = helper(inorder_root_idx + 1, in_right)
return root
return helper(0, len(inorder) - 1)BFS Traversal Variants
Level Order Zigzag Traversal
Modified Template: BFS level by level. Maintain level counter or boolean. For each level, collect nodes. If odd level, reverse list before adding to results. Or use deque's appendleft for one direction.
Example Problem: LeetCode 103. Binary Tree Zigzag Level Order Traversal.
from collections import deque
def zigzagLevelOrder(root):
if not root: return []
result = []
queue = deque([root])
left_to_right = True
while queue:
level_nodes_deque = deque() # Use deque for efficient append/prepend
level_size = len(queue)
for _ in range(level_size):
node = queue.popleft()
if left_to_right: level_nodes_deque.append(node.val)
else: level_nodes_deque.appendleft(node.val) # Prepend for R-L
if node.left: queue.append(node.left)
if node.right: queue.append(node.right)
result.append(list(level_nodes_deque))
left_to_right = not left_to_right
return resultLevel Order Right-Side View
Modified Template: BFS level by level. For each level, record the last node's value.
Example Problem: LeetCode 199. Binary Tree Right Side View.
// C++ example
vector<int> rightSideView(TreeNode* root) {
vector<int> view;
if (!root) return view;
queue<TreeNode*> q;
q.push(root);
while (!q.empty()) {
int level_size = q.size();
for(int i=0; i<level_size; ++i) {
TreeNode* node = q.front(); q.pop();
if (i == level_size - 1) view.push_back(node->val); // Last node
if (node->left) q.push(node->left);
if (node->right) q.push(node->right);
}
}
return view;
}Connecting Level Siblings (Next Pointers)
Modified Template: BFS level by level. For each level, link each node to the next node in queue (its right sibling). Set last node's next to null.
Example Problem: LeetCode 116/117. Populating Next Right Pointers in Each Node.
// Python, assuming Node class has 'next' pointer
def connect(root):
if not root: return None
q = deque([root])
while q:
prev_node_in_level = None
level_size = len(q)
for _ in range(level_size):
node = q.popleft()
if prev_node_in_level: prev_node_in_level.next = node
prev_node_in_level = node
if node.left: q.append(node.left)
if node.right: q.append(node.right)
if prev_node_in_level: prev_node_in_level.next = None # Last node in level
return rootInorder Traversal & BST Patterns
Validate BST (Inorder Check)
Modified Template: DFS inorder, keep track of previously seen value. If current value ≤ previous, BST property violated. Or, DFS with min/max bounds.
Example Problem: LeetCode 98. Validate Binary Search Tree.
// C++ example: DFS with min/max bounds
bool isValidBST_util(TreeNode* node, long minVal, long maxVal) {
if (!node) return true;
if (node->val <= minVal || node->val >= maxVal) return false;
return isValidBST_util(node->left, minVal, node->val) &&
isValidBST_util(node->right, node->val, maxVal);
}
bool isValidBST(TreeNode* root) {
return isValidBST_util(root, LONG_MIN, LONG_MAX);
}Kth Smallest Element (Inorder Ranking)
Modified Template: Inorder DFS with a counter. Decrement k (or increment count) when visiting node. Stop when counter hits k (or 0 if decrementing).
Example Problem: LeetCode 230. Kth Smallest Element in a BST.
// Java example: Iterative inorder
public int kthSmallest(TreeNode root, int k) {
Stack<TreeNode> stack = new Stack<>();
TreeNode curr = root;
while (curr != null || !stack.isEmpty()) {
while (curr != null) {
stack.push(curr);
curr = curr.left;
}
curr = stack.pop();
if (--k == 0) { return curr.val; }
curr = curr.right;
}
return -1; // Should not happen for valid k
}BST to Greater Sum Tree (Reverse Inorder Accumulation)
Modified Template: DFS visiting right subtree, then node, then left (reverse inorder). Maintain a global running sum. At each node, add its value to sum, then update node's value to current sum.
Example Problem: LeetCode 538. Convert BST to Greater Tree.
# Python example
class Solution:
total = 0
def convertBST(self, root: TreeNode) -> TreeNode:
if root:
self.convertBST(root.right)
self.total += root.val
root.val = self.total
self.convertBST(root.left)
return root
# Note: Reset self.total if calling multiple times on different trees with same Solution object.5. Interactive Animation (Pre-order Traversal)
The animation below demonstrates Pre-order Depth-First Search (DFS) on a sample binary tree. Observe how the algorithm visits the current node, then its left subtree, then its right subtree. The "call stack" visually represents the recursion depth.
- Visit 10. Stack: [10]. Order: [10].
- Go Left. Visit 5. Stack: [10, 5]. Order: [10, 5].
- Go Left. Visit 3. Stack: [10, 5, 3]. Order: [10, 5, 3]. (3 is leaf, backtrack)
- Back to 5. Go Right. Visit 7. Stack: [10, 5, 7]. Order: [10, 5, 3, 7]. (7 is leaf, backtrack)
- Back to 5 (done with children). Back to 10.
- Go Right. Visit 15. Stack: [10, 15]. Order: [10, 5, 3, 7, 15].
- Go Left (None). Go Right. Visit 18. Stack: [10, 15, 18]. Order: [10, 5, 3, 7, 15, 18]. (18 is leaf, backtrack)
- Done. Final Order: [10, 5, 3, 7, 15, 18].
6. Time & Space Complexity
For an n-node tree:
- Time Complexity (All Traversals): O(n) - each node visited once.
- Space Complexity (DFS - Recursive): O(h) for call stack, where h is tree height. Worst case O(n) for skewed tree, best/average O(log n) for balanced tree.
- Space Complexity (DFS - Iterative with Stack): O(h), similar to recursive.
- Space Complexity (BFS - Level-order): O(w) where w is max width of tree. Worst case O(n) for a complete tree.
(Output list space is O(n) if storing all node values.)
7. Common Pitfalls
- Incorrect or Missing Base Case: Not handling
Nonenodes in recursion. - Off-by-One Errors: In height/depth calculations.
- Infinite Recursion / Cycles: Usually not an issue for standard trees but be careful if modifying structure or treating as general graph.
- Null Child Handling: Accessing properties of
Nonechildren (e.g.,node.left.valwithout checkingnode.left). - Using Wrong Traversal Approach: E.g., using DFS for shortest path when BFS is better.
- Mistaking Binary Tree vs BST: Assuming BST properties for a general binary tree.
- BST Edge Cases: Incorrect min/max bounds for validation, mishandling duplicates.
- Not Accounting for Recursion Return Values: Forgetting to use or propagate results from recursive calls.
- Edge Cases & Skewed Trees: Test with empty, single-node, and skewed trees.
8. Frequently Asked Tree Problems (LeetCode)
The following are some of the most frequently asked LeetCode problems involving trees:
| Problem (LeetCode) | Difficulty |
|---|---|
| Maximum Depth of Binary Tree | Easy |
| Same Tree | Easy |
| Symmetric Tree | Easy |
| Balanced Binary Tree | Easy |
| Invert Binary Tree | Easy |
| Binary Tree Level Order Traversal | Medium |
| Binary Tree Zigzag Level Order Traversal | Medium |
| Binary Tree Right Side View | Medium |
| Validate Binary Search Tree | Medium |
| Subtree of Another Tree | Easy |
| Lowest Common Ancestor of a Binary Tree | Medium |
| Binary Tree Maximum Path Sum | Hard |
| Serialize and Deserialize Binary Tree | Hard |
| Construct Binary Tree from Preorder and Inorder Traversal | Medium |
| Path Sum | Easy |
| Kth Smallest Element in a BST | Medium |
Solving these problems will solidify your understanding of tree fundamentals.