Binary Tree
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def make_tree(values):
"""Build tree from level-order list (None = missing node)"""
if not values:
return None
root = TreeNode(values[0])
queue = [root]
i = 1
while queue and i < len(values):
node = queue.pop(0)
if i < len(values) and values[i] is not None:
node.left = TreeNode(values[i])
queue.append(node.left)
i += 1
if i < len(values) and values[i] is not None:
node.right = TreeNode(values[i])
queue.append(node.right)
i += 1
return root
Tree Traversals
DFS Traversals (Recursive)
def inorder(root):
"""Left → Root → Right (gives sorted order for BST)"""
if not root:
return []
return inorder(root.left) + [root.val] + inorder(root.right)
def preorder(root):
"""Root → Left → Right"""
if not root:
return []
return [root.val] + preorder(root.left) + preorder(root.right)
def postorder(root):
"""Left → Right → Root"""
if not root:
return []
return postorder(root.left) + postorder(root.right) + [root.val]
DFS Traversals (Iterative)
def inorder_iterative(root):
result = []
stack = []
curr = root
while curr or stack:
while curr:
stack.append(curr)
curr = curr.left
curr = stack.pop()
result.append(curr.val)
curr = curr.right
return result
def preorder_iterative(root):
if not root:
return []
result = []
stack = [root]
while stack:
node = stack.pop()
result.append(node.val)
if node.right:
stack.append(node.right)
if node.left:
stack.append(node.left)
return result
BFS (Level-Order)
from collections import deque
def level_order(root):
if not root:
return []
result = []
queue = deque([root])
while queue:
level = []
for _ in range(len(queue)):
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
# 3
# / \
# 9 20
# / \
# 15 7
tree = make_tree([3, 9, 20, None, None, 15, 7])
print(level_order(tree)) # [[3], [9, 20], [15, 7]]
Tree Properties
def max_depth(root):
"""Height of tree — O(n)"""
if not root:
return 0
return 1 + max(max_depth(root.left), max_depth(root.right))
def is_balanced(root):
"""Check if tree is height-balanced — O(n)"""
def check(node):
if not node:
return 0
left = check(node.left)
if left == -1:
return -1
right = check(node.right)
if right == -1:
return -1
if abs(left - right) > 1:
return -1
return 1 + max(left, right)
return check(root) != -1
def diameter(root):
"""Longest path between any two nodes — O(n)"""
max_dia = [0]
def depth(node):
if not node:
return 0
left = depth(node.left)
right = depth(node.right)
max_dia[0] = max(max_dia[0], left + right)
return 1 + max(left, right)
depth(root)
return max_dia[0]
def count_nodes(root):
if not root:
return 0
return 1 + count_nodes(root.left) + count_nodes(root.right)
Binary Search Tree (BST)
BST property: left subtree < node < right subtree
class BST:
def __init__(self):
self.root = None
def insert(self, val):
self.root = self._insert(self.root, val)
def _insert(self, node, val):
if not node:
return TreeNode(val)
if val < node.val:
node.left = self._insert(node.left, val)
elif val > node.val:
node.right = self._insert(node.right, val)
return node
def search(self, val):
return self._search(self.root, val)
def _search(self, node, val):
if not node or node.val == val:
return node
if val < node.val:
return self._search(node.left, val)
return self._search(node.right, val)
def delete(self, val):
self.root = self._delete(self.root, val)
def _delete(self, node, val):
if not node:
return None
if val < node.val:
node.left = self._delete(node.left, val)
elif val > node.val:
node.right = self._delete(node.right, val)
else:
# Node to delete found
if not node.left:
return node.right
if not node.right:
return node.left
# Two children: replace with inorder successor (min of right)
successor = node.right
while successor.left:
successor = successor.left
node.val = successor.val
node.right = self._delete(node.right, successor.val)
return node
def inorder(self):
return inorder(self.root)
BST Problems
def is_valid_bst(root, low=float('-inf'), high=float('inf')):
"""Validate BST"""
if not root:
return True
if root.val <= low or root.val >= high:
return False
return (is_valid_bst(root.left, low, root.val) and
is_valid_bst(root.right, root.val, high))
def lowest_common_ancestor_bst(root, p, q):
"""LCA in BST — O(log n) average"""
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
Heaps
Min-Heap Operations
class MinHeap:
def __init__(self):
self.heap = []
def push(self, val):
self.heap.append(val)
self._sift_up(len(self.heap) - 1)
def pop(self):
if len(self.heap) == 1:
return self.heap.pop()
min_val = self.heap[0]
self.heap[0] = self.heap.pop()
self._sift_down(0)
return min_val
def _sift_up(self, i):
parent = (i - 1) // 2
while i > 0 and self.heap[i] < self.heap[parent]:
self.heap[i], self.heap[parent] = self.heap[parent], self.heap[i]
i = parent
parent = (i - 1) // 2
def _sift_down(self, i):
n = len(self.heap)
while True:
left = 2 * i + 1
right = 2 * i + 2
smallest = i
if left < n and self.heap[left] < self.heap[smallest]:
smallest = left
if right < n and self.heap[right] < self.heap[smallest]:
smallest = right
if smallest == i:
break
self.heap[i], self.heap[smallest] = self.heap[smallest], self.heap[i]
i = smallest
Exercises
Exercise 1: Path Sum
Check if there's a root-to-leaf path that sums to target.
Solution:
def has_path_sum(root, target):
if not root:
return False
if not root.left and not root.right:
return root.val == target
return (has_path_sum(root.left, target - root.val) or
has_path_sum(root.right, target - root.val))
Exercise 2: Right Side View
Return values visible from the right side (rightmost node at each level).
Solution:
from collections import deque
def right_side_view(root):
if not root:
return []
result = []
queue = deque([root])
while queue:
for i in range(len(queue)):
node = queue.popleft()
if i == len(queue): # last node at this level
result.append(node.val)
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
# Actually: just take the last node per level
# Corrected:
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)
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
return result
Exercise 3: Serialize and Deserialize Binary Tree
Convert a tree to string and back.
Solution:
def serialize(root):
if not root:
return "null"
return f"{root.val},{serialize(root.left)},{serialize(root.right)}"
def deserialize(data):
values = iter(data.split(","))
def build():
val = next(values)
if val == "null":
return None
node = TreeNode(int(val))
node.left = build()
node.right = build()
return node
return build()