Tree problems: DFS (preorder/inorder/postorder) and BFS (level order). Most tree problems require visiting every node exactly once — understand the recursive structure.
Problems: 15
Easy: 6
Medium: 7
Hard: 2
Learning approach: Read the problem. Try the test cases yourself first.
Click Hint if stuck — it guides without spoiling.
Use Show Solution only after a genuine attempt.
Then hit Let's Code to run your solution live.
The diameter through a node = height(left) + height(right). Compute both at every node and track the global max.
Python Solution
def diameterOfBinaryTree(root):
result = [0]
def dfs(node):
if not node:
return 0
left = dfs(node.left)
right = dfs(node.right)
result[0] = max(result[0], left + right) # update global max
return 1 + max(left, right) # return height
dfs(root)
return result[0]
Key idea: DFS returns the height of each subtree. The diameter through any node is left_height + right_height. Use a nonlocal variable to track the maximum across all nodes.
Combine the balance check with height computation. Return -1 from DFS to signal 'unbalanced subtree' — this short-circuits further work.
Python Solution
def isBalanced(root):
def height(node):
if not node:
return 0
left = height(node.left)
if left == -1: return -1 # already imbalanced
right = height(node.right)
if right == -1: return -1
if abs(left - right) > 1:
return -1 # current node is unbalanced
return 1 + max(left, right)
return height(root) != -1
Key idea: DFS that returns the height, but uses -1 as a sentinel for 'unbalanced'. Once -1 is returned it propagates up, avoiding redundant computation.
Compare roots. Then recursively compare left subtrees and right subtrees.
Python Solution
def isSameTree(p, q):
if not p and not q:
return True # both null — same
if not p or not q:
return False # one null, one not — different
return (p.val == q.val
and isSameTree(p.left, q.left)
and isSameTree(p.right, q.right))
Key idea: Three base cases: (1) both null → True, (2) one null → False, (3) values match → recurse on both subtrees.
At every node in root, check if the tree rooted there is identical to subRoot.
Python Solution
def isSubtree(root, subRoot):
def isSame(p, q):
if not p and not q: return True
if not p or not q: return False
return (p.val == q.val
and isSame(p.left, q.left)
and isSame(p.right, q.right))
if not root:
return False
if isSame(root, subRoot):
return True
return isSubtree(root.left, subRoot) or isSubtree(root.right, subRoot)
Key idea: DFS through root. At each node, check if the subtree rooted there matches subRoot using an isSameTree helper.
Given BST root and two nodes p and q, find their Lowest Common Ancestor.
Test Cases
LCA of BST([6,2,8,0,4,7,9], p=2, q=8) → 6
LCA of BST([6,2,8,0,4,7,9], p=2, q=4) → 2
BST propertyiterativeO(h)
Use the BST property: if both p and q are less than current node, go left. If both greater, go right. Otherwise, current is the LCA.
Python Solution
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 or one equals root
Key idea: In a BST, if both nodes are smaller, the LCA is in the left subtree. If both larger, it's in the right. If they straddle the current node (or one equals it), the current node is the LCA.
Use a queue. At each level, process exactly len(queue) nodes (snapshot the size first so new children don't get counted in the current level).
Python Solution
from collections import deque
def levelOrder(root):
if not root:
return []
result = []
queue = deque([root])
while queue:
level = []
for _ in range(len(queue)): # process only current-level nodes
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
Key idea: BFS with a queue. Before processing a level, snapshot len(queue) — that's how many nodes belong to the current level. Children added during processing belong to the next level.
Time: O(n). Space: O(n) — queue holds at most one full level.
BFS level order — for each level, just keep the last node's value.
Python Solution
from collections import deque
def rightSideView(root):
if not root:
return []
result = []
queue = deque([root])
while queue:
level_size = len(queue)
for i in range(level_size):
node = queue.popleft()
if i == level_size - 1:
result.append(node.val) # last node in this level
if node.left: queue.append(node.left)
if node.right: queue.append(node.right)
return result
Key idea: BFS level order. For each level, record only the last node (index == level_size - 1). That's the node visible from the right.
Pass bounds (low, high) down the tree. Every node must satisfy low < node.val < high.
Python Solution
def isValidBST(root):
def validate(node, low, high):
if not node:
return True
if not (low < node.val < high):
return False
return (validate(node.left, low, node.val)
and validate(node.right, node.val, high))
return validate(root, float('-inf'), float('inf'))
Key idea: DFS passing valid range [low, high] for each node. Going left narrows the upper bound to the current value; going right narrows the lower bound.
In-order traversal of a BST yields values in sorted order. The k-th element in the in-order traversal is the answer.
Python Solution
def kthSmallest(root, k):
stack = []
curr = root
count = 0
while curr or stack:
while curr: # go as far left as possible
stack.append(curr)
curr = curr.left
curr = stack.pop() # visit node (in sorted order)
count += 1
if count == k:
return curr.val
curr = curr.right # move to right subtree
Key idea: Iterative in-order traversal (Left-Root-Right) visits BST nodes in ascending order. Stop and return when we've counted k nodes.
preorder[0] is rootinorder index splitsrecursive divide
The first element of preorder is the root. Find it in inorder — everything to its left is the left subtree, everything to the right is the right subtree.
Python Solution
def buildTree(preorder, inorder):
if not preorder:
return None
root_val = preorder[0]
root = TreeNode(root_val)
mid = inorder.index(root_val) # split point
root.left = buildTree(preorder[1:mid+1], inorder[:mid])
root.right = buildTree(preorder[mid+1:], inorder[mid+1:])
return root
Key idea: The first element of preorder is always the root. Use inorder to find how many nodes are in the left subtree (everything before the root's position), then recurse.
Time: O(n²) naive. O(n) with a hash map for inorder indices. Space: O(n).
For each node, compute the max 'gain' from that side (clamped to 0 to ignore negative paths). The diameter through the node is node.val + left_gain + right_gain.
Python Solution
def maxPathSum(root):
result = [float('-inf')]
def dfs(node):
if not node:
return 0
left = max(0, dfs(node.left)) # clamp negative gains to 0
right = max(0, dfs(node.right))
# Update global max for path through this node
result[0] = max(result[0], node.val + left + right)
# Return max gain going UP (can only use one branch)
return node.val + max(left, right)
dfs(root)
return result[0]
Key idea: DFS returns the max gain going upward (one branch only). But the max path SUM through a node uses both branches. Clamp gains to 0 to gracefully skip negative subtrees.
Design an algorithm to serialize a binary tree to a string and deserialize it back. No constraints on the format.
Test Cases
codec = Codec()
root = build_tree([1,2,3,null,null,4,5])
result = codec.deserialize(codec.serialize(root))
# result has same structure as root
preorder DFScomma-separatedN for null
Use preorder (root, left, right) DFS. Represent null nodes with a sentinel like 'N'. Deserialize by consuming tokens from the iterator.
Python Solution
class Codec:
def serialize(self, root):
# Preorder: root, left, right. 'N' for null.
if not root:
return 'N'
return f'{root.val},{self.serialize(root.left)},{self.serialize(root.right)}'
def deserialize(self, data):
vals = iter(data.split(','))
def build():
val = next(vals)
if val == 'N':
return None
node = TreeNode(int(val))
node.left = build()
node.right = build()
return node
return build()
Key idea: Preorder DFS produces a string with null markers. Deserialization consumes tokens with a recursive builder — preorder naturally reconstructs the tree without needing inorder.