NeetCode 150 · Trees

Trees Problems

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.
01 Easy TreeDFSBFS
Given root of a binary tree, invert the tree and return its root.
Test Cases
Invert([4,2,7,1,3,6,9]) → [4,7,2,9,6,3,1]
recursive swappost-orderO(n)
To invert a tree, swap the left and right children, then recursively invert each subtree.
Python Solution
class TreeNode: def __init__(self, val=0, left=None, right=None): self.val = val; self.left = left; self.right = right def invertTree(root): if not root: return None # Swap children, then recursively invert root.left, root.right = invertTree(root.right), invertTree(root.left) return root
Key idea: Post-order DFS: invert both subtrees, then swap. Alternatively, swap first then recurse — both work.
Time: O(n).
Space: O(h) — recursion depth equals tree height.
02 Easy TreeDFSBFS
Given root of a binary tree, return its maximum depth (length of the longest path from root to a leaf).
Test Cases
maxDepth([3,9,20,null,null,15,7]) → 3 maxDepth([1,null,2]) → 2
recursive DFS1 + max(left, right)O(n)
What's the base case? What's the relationship between a node's depth and its children's depths?
Python Solution
def maxDepth(root): if not root: return 0 return 1 + max(maxDepth(root.left), maxDepth(root.right))
Key idea: The depth of a node is 1 + the maximum depth of its two children. Base case: a null node has depth 0.
Time: O(n).
Space: O(h).
03 Easy TreeDFS
Given root of a binary tree, return the length of the diameter — the longest path between any two nodes (measured in edges).
Test Cases
diameterOfBinaryTree([1,2,3,4,5]) → 3 # path 4-2-1-3 diameterOfBinaryTree([1,2]) → 1
DFS heighttrack max left+rightO(n)
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.
Time: O(n).
Space: O(h).
04 Easy TreeDFS
Given root of a binary tree, determine if it is height-balanced (every node's left and right subtrees differ in height by at most 1).
Test Cases
isBalanced([3,9,20,null,null,15,7]) → True isBalanced([1,2,2,3,3,null,null,4,4]) → False
DFS returns -1 on imbalanceheight sentinelO(n)
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.
Time: O(n).
Space: O(h).
05 Easy TreeDFSBFS
Given roots of two binary trees p and q, check if they are the same (structurally identical with the same node values).
Test Cases
isSameTree([1,2,3], [1,2,3]) → True isSameTree([1,2], [1,null,2]) → False
recursive comparisonbase cases for nullO(n)
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.
Time: O(n).
Space: O(h).
06 Easy TreeDFSString Matching
Given roots of trees root and subRoot, return True if subRoot is a subtree of root.
Test Cases
isSubtree([3,4,5,1,2], [4,1,2]) → True isSubtree([3,4,5,1,2,null,null,null,null,0], [4,1,2]) → False
DFS at each nodeisSameTree helperO(m·n)
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.
Time: O(m·n).
Space: O(h).
07 Medium TreeBSTDFS
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.
Time: O(h) — O(log n) balanced, O(n) worst.
Space: O(1).
08 Medium TreeBFS
Given root of a binary tree, return the level order traversal of its nodes' values (i.e., from left to right, level by level).
Test Cases
levelOrder([3,9,20,null,null,15,7]) → [[3],[9,20],[15,7]]
BFS with dequelevel size snapshotO(n)
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.
09 Medium TreeBFSDFS
Given root of a binary tree, imagine looking from the right side. Return the values of nodes you can see (the rightmost node of each level).
Test Cases
rightSideView([1,2,3,null,5,null,4]) → [1,3,4] rightSideView([1,null,3]) → [1,3]
BFS level last nodedeque level snapshotO(n)
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.
Time: O(n).
Space: O(n).
10 Medium TreeDFS
Given root of binary tree, count the number of 'good' nodes — nodes where the path from root to that node has no node with a greater value.
Test Cases
goodNodes([3,1,4,3,null,1,5]) → 4 goodNodes([3,3,null,4,2]) → 3
DFS with max_so_farpreorderO(n)
Pass the maximum value seen on the path from root to the current node. If current value >= max, it's a good node.
Python Solution
def goodNodes(root): def dfs(node, max_so_far): if not node: return 0 is_good = 1 if node.val >= max_so_far else 0 new_max = max(max_so_far, node.val) return is_good + dfs(node.left, new_max) + dfs(node.right, new_max) return dfs(root, float('-inf'))
Key idea: DFS carrying the maximum value seen on the current path. A node is 'good' if its value ≥ max_so_far. Accumulate the count from all subtrees.
Time: O(n).
Space: O(h).
11 Medium TreeDFSBST
Given root of a binary tree, determine if it is a valid binary search tree.
Test Cases
isValidBST([2,1,3]) → True isValidBST([5,1,4,null,null,3,6]) → False
DFS with boundsmin/max rangeO(n)
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.
Time: O(n).
Space: O(h).
12 Medium TreeDFSBST
Given root of a BST and integer k, return the k-th smallest value.
Test Cases
kthSmallest([3,1,4,null,2], 1) → 1 kthSmallest([5,3,6,2,4,null,null,1], 3) → 3
iterative in-orderstack-based DFSO(H+k)
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.
Time: O(H+k).
Space: O(H) — H is tree height.
13 Medium TreeDFSDivide and Conquer
Given two integer arrays preorder and inorder, construct and return the binary tree.
Test Cases
buildTree([3,9,20,15,7], [9,3,15,20,7]) → Tree: [3,9,20,null,null,15,7]
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).
14 Hard TreeDFSDP
Given root of a binary tree, find the maximum path sum. The path must contain at least one node and does not need to go through the root.
Test Cases
maxPathSum([1,2,3]) → 6 maxPathSum([-10,9,20,null,null,15,7]) → 42
DFS gainmax(0, gain) to skip negativesglobal max
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.
Time: O(n).
Space: O(h).
15 Hard TreeDFSBFSDesign
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.
Time: O(n).
Space: O(n).
← Prev Category Next Category →