Day 3 · Topic 1 · Most Important for SDE 2
Trees
DFS (Recursive)
Path problems, depth, structure
BFS (Queue)
Level-by-level, shortest path, right side view
BST Property
L < root < R at every node
Easy Maximum Depth of Binary Tree
def maxDepth(root):
if not root: return 0
return 1 + max(maxDepth(root.left), maxDepth(root.right))
# Base case: null = depth 0. Recurse both sides. Easy Diameter of Binary Tree
INSIGHT: Diameter through node = left depth + right depth. Track globally. Path may not go through root.
def diameterOfBinaryTree(root):
max_d = [0]
def depth(node):
if not node: return 0
l, r = depth(node.left), depth(node.right)
max_d[0] = max(max_d[0], l + r)
return 1 + max(l, r)
depth(root)
return max_d[0] Medium Validate Binary Search Tree
INSIGHT: Pass min/max bounds as you recurse. Left child must be less than parent; right child must be greater. Common mistake: checking only immediate parent.
def isValidBST(root):
def validate(node, min_val, max_val):
if not node: return True
if node.val <= min_val or node.val >= max_val:
return False
return (validate(node.left, min_val, node.val) and
validate(node.right, node.val, max_val))
return validate(root, float('-inf'), float('inf')) Medium Binary Tree Level Order Traversal (BFS)
from collections import deque
def levelOrder(root):
if not root: return []
result = []
queue = deque([root])
while queue:
level = []
for _ in range(len(queue)): # process exactly one level
node = queue.popleft()
level.append(node.val)
if node.left: queue.append(node.left)
if node.right: queue.append(node.right)
result.append(level)
return result Medium Lowest Common Ancestor of BST
INSIGHT: Use BST property. If both p and q are less than root → go left. If both greater → go right. Otherwise current node is LCA (split point).
def lowestCommonAncestor(root, p, q):
while root:
if p.val < root.val and q.val < root.val:
root = root.left
elif p.val > root.val and q.val > root.val:
root = root.right
else:
return root # split point = LCA
# Time: O(h) where h = height. O(log n) for balanced BST. Hard Binary Tree Maximum Path Sum
INSIGHT: At each node: (1) candidate = node + left + right (can't go up). (2) return to parent = node + max(left, right) (can only go one direction upward). Ignore negative contributions.
def maxPathSum(root):
max_sum = [float('-inf')]
def dfs(node):
if not node: return 0
left = max(dfs(node.left), 0) # discard negative subtrees
right = max(dfs(node.right), 0)
max_sum[0] = max(max_sum[0], node.val + left + right)
return node.val + max(left, right) # return max gain going up
dfs(root)
return max_sum[0] Hard Serialize and Deserialize Binary Tree
class Codec:
def serialize(self, root):
out = []
def dfs(node):
if not node: out.append('N'); return
out.append(str(node.val))
dfs(node.left); dfs(node.right)
dfs(root)
return ','.join(out)
def deserialize(self, data):
vals = iter(data.split(','))
def dfs():
val = next(vals)
if val == 'N': return None
node = TreeNode(int(val))
node.left = dfs(); node.right = dfs()
return node
return dfs()
# Preorder DFS preserves structure. 'N' marks null nodes. Medium Construct Tree from Preorder + Inorder
INSIGHT: preorder[0] = root. Find root in inorder → splits into left and right subtrees. Sizes tell you how to slice preorder too.
def buildTree(preorder, inorder):
if not preorder or not inorder: return None
root = TreeNode(preorder[0])
mid = inorder.index(preorder[0]) # split point
root.left = buildTree(preorder[1:mid+1], inorder[:mid])
root.right = buildTree(preorder[mid+1:], inorder[mid+1:])
return root