Ai-CompTech

AI Computing

Computer Science Fundamentals

Trees and Binary Search Trees

Master hierarchical data structures and tree algorithms

Advanced 80 min read 0 examples 0 quiz questionsID: 6962f8f9
Lesson Content

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

code
class 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)

code
def 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)

code
def 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)

code
def 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)

code
from 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

  1. Left subtree values < parent value
  2. Right subtree values > parent value
  3. Each subtree is also a BST
  4. No duplicate values (usually)
code
8 / \ 3 10 / \ \ 1 6 14 / \ / 4 7 13

BST Operations

1. Search

code
def 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

code
def 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

code
def 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

code
def height(root): if not root: return 0 return 1 + max(height(root.left), height(root.right))

2. Count Nodes

code
def count_nodes(root): if not root: return 0 return 1 + count_nodes(root.left) + count_nodes(root.right)

3. Check if BST

code
def 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

code
def 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

  1. Maximum depth of binary tree
  2. Invert/mirror binary tree
  3. Serialize and deserialize BST
  4. Validate BST
  5. Kth smallest element in BST
  6. Binary tree level order traversal
  7. Path sum problems
  8. Construct tree from traversals