Trees
6 min read
data-structurestreescs-fundamentalsinterview-prep
A hierarchical data structure of nodes connected by edges. Every node has one parent (except the root) and zero or more children. No cycles.
text
10
/ \
5 15
/ \ / \
3 7 12 20
/ \ / \
1 4 6 9
text
Level 0 10 ← Root
/ \
Level 1 5 15 ← Internal
/ \ / \
Level 2 3 7 12 20 ← Internal
/ \ / \
Level 3 1 4 6 9 ← Leaves
Rule: Left < Parent < Right
Terminology
| Term | Definition |
|---|---|
| Root | Top node — no parent |
| Leaf | Node with no children |
| Height | Longest path from root to a leaf |
| Depth | Distance from root to a node |
| Subtree | Node + all its descendants |
| Degree | Number of children a node has |
Types of Trees
| Type | Property |
|---|---|
| Binary Tree | Each node has at most 2 children |
| Binary Search Tree (BST) | Left < Parent < Right |
| Balanced BST (AVL, Red-Black) | Height kept at O(log n) |
| Complete Binary Tree | All levels full except last, filled left to right |
| Full Binary Tree | Every node has 0 or 2 children |
| N-ary Tree | Each node has at most N children |
| Trie | Prefix tree for string storage |
| Heap | Complete tree with heap property (min/max) |
Node Structure
text
Node:
value
left → Node | null
right → Node | null
Tree Traversals
Four ways to visit every node. Order of output differs per traversal.
Inorder (Left → Root → Right)
Produces sorted output on a BST.
text
inorder(node):
if node == null: return
inorder(node.left)
visit(node)
inorder(node.right)
Preorder (Root → Left → Right)
Used to copy or serialize a tree.
text
preorder(node):
if node == null: return
visit(node)
preorder(node.left)
preorder(node.right)
Postorder (Left → Right → Root)
Used to delete or evaluate a tree (expression trees).
text
postorder(node):
if node == null: return
postorder(node.left)
postorder(node.right)
visit(node)
Level-order (BFS)
Visits nodes level by level using a queue.
text
levelOrder(root):
queue = [root]
while queue not empty:
node = queue.dequeue()
visit(node)
if node.left: queue.enqueue(node.left)
if node.right: queue.enqueue(node.right)
| Traversal | Time | Space |
|---|---|---|
| All four | O(n) | O(h) DFS / O(w) BFS |
h = tree height, w = max width. Worst case O(n) space for skewed tree (DFS) or full last level (BFS).
Binary Search Tree (BST)
Search
text
search(node, val):
if node == null: return null
if val == node.value: return node
if val < node.value: return search(node.left, val)
else: return search(node.right, val)
Insert
text
insert(node, val):
if node == null: return Node(val)
if val < node.value: node.left = insert(node.left, val)
else: node.right = insert(node.right, val)
return node
Delete
Three cases:
- Leaf node: remove directly
- One child: replace node with its child
- Two children: replace with inorder successor (smallest in right subtree), then delete successor
text
delete(node, val):
if node == null: return null
if val < node.value: node.left = delete(node.left, val)
elif val > node.value: node.right = delete(node.right, val)
else:
if node.left == null: return node.right
if node.right == null: return node.left
successor = findMin(node.right)
node.value = successor.value
node.right = delete(node.right, successor.value)
return node
| Operation | Average (Balanced) | Worst (Skewed) |
|---|---|---|
| Search | O(log n) | O(n) |
| Insert | O(log n) | O(n) |
| Delete | O(log n) | O(n) |
| Space | O(n) | O(n) |
A skewed BST degrades to a linked list. Use a self-balancing BST (AVL, Red-Black) to guarantee O(log n).
Balanced BST
Self-balancing trees maintain height ≈ log n after every insert/delete.
| Type | Balance Condition | Rotations | Use Case |
|---|---|---|---|
| AVL Tree | height(L) - height(R) | ≤ 1 | |
| Red-Black Tree | No two consecutive red nodes; black-height equal | Max 2 rotations | Java TreeMap, TreeSet |
text
// AVL rotation (Left-Left case)
rotateRight(y):
x = y.left
y.left = x.right
x.right = y
update heights
return x
Height of a Tree
text
height(node):
if node == null: return -1
return 1 + max(height(node.left), height(node.right))
| Time | Space | |
|---|---|---|
| Complexity | O(n) | O(h) |
Check Balanced Tree
A tree is balanced if every node's left and right subtree heights differ by at most 1.
text
isBalanced(node):
if node == null: return true
lh = height(node.left)
rh = height(node.right)
if abs(lh - rh) > 1: return false
return isBalanced(node.left) and isBalanced(node.right)
| Time | Space | |
|---|---|---|
| Complexity | O(n) | O(h) |
Lowest Common Ancestor (LCA)
Classic interview problem. Deepest node that is an ancestor of both p and q.
text
lca(node, p, q):
if node == null: return null
if node == p or node == q: return node
left = lca(node.left, p, q)
right = lca(node.right, p, q)
if left and right: return node // p and q on opposite sides
return left if left else right
| Time | Space | |
|---|---|---|
| Complexity | O(n) | O(h) |
Trie (Prefix Tree)
Each node represents one character. Used for autocomplete, spell check, IP routing.
text
TrieNode:
children[26] // or HashMap
isEndOfWord = false
insert(word):
curr = root
for ch in word:
if ch not in curr.children:
curr.children[ch] = TrieNode()
curr = curr.children[ch]
curr.isEndOfWord = true
search(word):
curr = root
for ch in word:
if ch not in curr.children: return false
curr = curr.children[ch]
return curr.isEndOfWord
| Operation | Time | Space |
|---|---|---|
| Insert | O(m) | O(m) |
| Search | O(m) | O(1) |
m = length of the word.
Quick Reference
| Structure | Search | Insert | Delete | Space | Notes |
|---|---|---|---|---|---|
| Binary Tree | O(n) | O(n) | O(n) | O(n) | No ordering guarantee |
| BST | O(log n) avg | O(log n) avg | O(log n) avg | O(n) | Degrades on skewed input |
| AVL Tree | O(log n) | O(log n) | O(log n) | O(n) | Strict balance, more rotations |
| Red-Black Tree | O(log n) | O(log n) | O(log n) | O(n) | Looser balance, fewer rotations |
| Trie | O(m) | O(m) | O(m) | O(n·m) | String keys only |
| Heap | O(n) | O(log n) | O(log n) | O(n) | Priority access only |