Trees
A tree is a hierarchical data structure consisting of nodes connected by edges, with one root node at the top. It does not contain cycles and is widely used to represent hierarchical relationships like file systems, organizational charts, XML/JSON, and search structures such as BSTs and heaps.
Trees enable fast searching, insertion, and deletion depending on the tree type, often improving performance over linear structures.
Take a moment to review key terms having to do with trees.
- Leaf node: A node that doesn’t have any children.
- Root node: The topmost node in a tree. Note that this will almost always be the node you are given when implementing an algorithm to manipulate a tree.
- Height: The distance between the root node and the lowest leaf node.
- Subtree: A node beneath the root node and all of its descendants. Each node is in effect the root node of its own subtree.
Types of trees
1. Binary Tree
A binary tree is a tree where each node has at most two children: left and right. It is the foundation of many advanced structures like BST, AVL, and heaps.
Used for:
- Level order traversal
- Structural tree problems
- Recursive tree questions
2. Binary Search Tree (BST)
A BST is a binary tree where:
- Left subtree contains values smaller than the node.
- Right subtree contains values larger than the node.
- BST enables fast lookup with O(log n) average case.
Used for:
- Search problems
- Lowest Common Ancestor (LCA)
- Insert/search/delete operations
- Maintaining sorted data
3. Trie (Prefix Tree)
A tree used to store strings where each node represents a character.
Used for:
- Autocomplete
- Spell check
- Longest prefix problems
- Word search
Tree traversals & common operations
It's possible to use both depth-first search and breadth-first search on trees. Depth-first search on a tree requires a series of recursive calls. There are a few different orders to choose from.
- Pre-order traversal, where each recursive call:
- Traverses the current subtree
- Visits the left node
- Traverse the right subtree
def preorder(root):
if not root:
return
print(root.val)
preorder(root.left)
preorder(root.right)- In-order traversal, where each recursive call:
- Traverses the left subtree
- Visits the current node
- Traverses the right subtree
def inorder(root):
if not root:
return
inorder(root.left)
print(root.val)
inorder(root.right)- Post-order reversal, where each recursive call:
- Traverses the left subtree
- Traverses the right subtree
- Traverses the current subtree
def postorder(root):
if not root:
return
postorder(root.left)
postorder(root.right)
print(root.val)- Level order traversal
A breadth-first tree traversal is called a level-order traversal. This algorithm is not performed recursively. Instead, it works by visiting the current node, placing its children nodes in a queue, and then while the queue is nonempty, dequeuing the next node and repeating the first two steps.
from collections import deque
def level_order(root):
if not root:
return
q = deque([root])
while q:
node = q.popleft()
print(node.val)
if node.left: q.append(node.left)
if node.right: q.append(node.right)- Height of a binary tree
def height(root):
if not root:
return 0
return 1 + max(height(root.left), height(root.right))- Insert in a binary search tree (BST)
def insert_bst(root, val):
if not root:
return TreeNode(val)
if val < root.val:
root.left = insert_bst(root.left, val)
else:
root.right = insert_bst(root.right, val)
return root
Common edge cases & pitfalls
-
Not handling empty tree / null root
-
Skipping base case in recursion can lead to infinite recursion
-
Assuming tree is always balanced
-
Forgetting to update parent pointers (in iterative BST)
-
Wrong traversal order in DFS (pre/in/post)
-
Not considering skewed tree case →
O(n) -
Mishandling duplicates in BST
Quiz
- Which traversal processes nodes in sorted order for a BST?
a) Preorder
b) Postorder
c) Inorder
d) Level order
- What makes AVL trees different from normal BSTs?
a) They allow duplicates
b) They store keys as hashes
c) They maintain height balance using rotations
d) They use BFS for search
- Which tree is best for implementing a priority queue?
a) Trie
b) BST
c) Heap
d) Segment tree