
AI Computing
Trees and Binary Search Trees
Tree Basics
Definition
A hierarchical data structure with nodes connected by edges. One root node, with child nodes forming a hierarchy.
Tree Terminology
- Root: Top node (no parent)
- Parent: Node with children
- Child: Node under a parent
- Leaf: Node with no children
- Edge: Connection between nodes
- Path: Sequence of nodes connected by edges
- Height: Longest path from root to leaf
- Depth: Distance from root to node
- Level: Depth + 1
- Subtree: Tree formed by a node and its descendants
- Degree: Number of children of a node
Node Structure
codeclass TreeNode: def __init__(self, value): self.value = value self.children = [] # For general tree # OR for binary tree: self.left = None self.right = None
Binary Trees
Definition
A tree where each node has at most 2 children (left and right).
Types of Binary Trees
1. Full Binary Tree
Every node has 0 or 2 children (no node has 1 child)
2. Complete Binary Tree
All levels filled except possibly last, filled left-to-right
3. Perfect Binary Tree
All internal nodes have 2 children, all leaves at same level
4. Balanced Binary Tree
Height difference between left and right subtrees ≤ 1
Tree Traversals
1. Inorder (Left, Root, Right)
codedef inorder(root): if root: inorder(root.left) print(root.value, end=" ") inorder(root.right)
Output: 4 2 5 1 6 3 7 (sorted for BST)
2. Preorder (Root, Left, Right)
codedef preorder(root): if root: print(root.value, end=" ") preorder(root.left) preorder(root.right)
Output: 1 2 4 5 3 6 7 (used for copying)
3. Postorder (Left, Right, Root)
codedef postorder(root): if root: postorder(root.left) postorder(root.right) print(root.value, end=" ")
Output: 4 5 2 6 7 3 1 (used for deletion)
4. Level Order (BFS)
codefrom collections import deque def level_order(root): if not root: return queue = deque([root]) while queue: node = queue.popleft() print(node.value, end=" ") if node.left: queue.append(node.left) if node.right: queue.append(node.right)
Output: 1 2 3 4 5 6 7 (level by level)
Binary Search Tree (BST)
Properties
- Left subtree values < parent value
- Right subtree values > parent value
- Each subtree is also a BST
- No duplicate values (usually)
code8 / \ 3 10 / \ \ 1 6 14 / \ / 4 7 13
BST Operations
1. Search
codedef search(root, key): # Base cases if not root or root.value == key: return root # Key is smaller, go left if key < root.value: return search(root.left, key) # Key is larger, go right return search(root.right, key)
Time: O(h) where h = height
2. Insert
codedef insert(root, key): if not root: return TreeNode(key) if key < root.value: root.left = insert(root.left, key) elif key > root.value: root.right = insert(root.right, key) return root
Time: O(h)
3. Delete
codedef delete(root, key): if not root: return root # Find node to delete if key < root.value: root.left = delete(root.left, key) elif key > root.value: root.right = delete(root.right, key) else: # Node found - 3 cases: # Case 1: No children (leaf) if not root.left and not root.right: return None # Case 2: One child if not root.left: return root.right if not root.right: return root.left # Case 3: Two children # Find inorder successor (smallest in right subtree) successor = find_min(root.right) root.value = successor.value root.right = delete(root.right, successor.value) return root def find_min(node): while node.left: node = node.left return node
BST Advantages
✅ Efficient search: O(log n) average ✅ Maintains sorted order ✅ Dynamic size ✅ Efficient insert/delete
BST Disadvantages
❌ Can become unbalanced (O(n) worst case) ❌ No O(1) operations ❌ More complex than arrays
Time Complexity Summary
| Operation | Average | Worst Case | |-----------|---------|------------| | Search | O(log n) | O(n) | | Insert | O(log n) | O(n) | | Delete | O(log n) | O(n) | | Traversal | O(n) | O(n) |
Worst case: skewed tree (essentially a linked list)
Balanced Trees
To guarantee O(log n) operations:
AVL Tree
- Self-balancing BST
- Height difference between subtrees ≤ 1
- Uses rotations to maintain balance
Red-Black Tree
- Self-balancing BST
- Each node colored red or black
- Rules ensure approximate balance
- Used in Java TreeMap, C++ std::map
Common Tree Problems
1. Find Height
codedef height(root): if not root: return 0 return 1 + max(height(root.left), height(root.right))
2. Count Nodes
codedef count_nodes(root): if not root: return 0 return 1 + count_nodes(root.left) + count_nodes(root.right)
3. Check if BST
codedef is_bst(root, min_val=float('-inf'), max_val=float('inf')): if not root: return True if root.value <= min_val or root.value >= max_val: return False return (is_bst(root.left, min_val, root.value) and is_bst(root.right, root.value, max_val))
4. Lowest Common Ancestor
codedef lca_bst(root, n1, n2): if not root: return None if n1 < root.value and n2 < root.value: return lca_bst(root.left, n1, n2) if n1 > root.value and n2 > root.value: return lca_bst(root.right, n1, n2) return root
Real-World Applications
- File Systems: Directory structure
- HTML DOM: Web page structure
- Databases: B-trees for indexing
- Compilers: Abstract Syntax Trees
- Router Tables: IP routing
- Decision Trees: Machine learning
- Org Charts: Company hierarchy
Practice Problems
- Maximum depth of binary tree
- Invert/mirror binary tree
- Serialize and deserialize BST
- Validate BST
- Kth smallest element in BST
- Binary tree level order traversal
- Path sum problems
- Construct tree from traversals