Unit III: Trees
1. Introduction to Trees
A Tree is a non-linear hierarchical data structure that consists of nodes connected by edges. Unlike linear structures (arrays, lists), trees represent relationships like "parent-child" hierarchies.
- Root: The topmost node of the tree.
- Leaf: A node with no children.
- Height: The length of the longest path from the root to a leaf.
2. Binary Search Trees (BST)
A Binary Tree is a tree where each node has at most two children (Left and Right). A Binary Search Tree (BST) is specialized such that:
- The left subtree of a node contains only nodes with keys less than the node’s key.
- The right subtree of a node contains only nodes with keys greater than the node’s key.
Operations on BST
- Insertion: Compares the value with the root; if smaller, it moves to the left; if larger, it moves to the right until an empty spot is found.
- Deletion: More complex; involves three cases: deleting a leaf, deleting a node with one child, or deleting a node with two children (requires replacing with in-order successor or predecessor).
3. Tree Traversals
Traversal is the process of visiting all nodes in a tree exactly once. These can be implemented Recursively or Iteratively.
| Traversal Type | Order of Visitation |
|---|---|
| In-order | Left Subtree → Root → Right Subtree |
| Pre-order | Root → Left Subtree → Right Subtree |
| Post-order | Left Subtree → Right Subtree → Root |
Exam Tip: In-order BST
Performing an In-order traversal on a Binary Search Tree always yields the elements in ascending sorted order.
4. Threaded Binary Trees
Standard binary trees have many NULL pointers in leaf nodes. Threaded Binary Trees utilize these NULL pointers to point to the in-order predecessor or successor.
- Advantage: Enables faster traversal without using a stack or recursion.
- Operations: Supports Insertion, Deletion, and Traversals.
5. Height-Balanced (AVL) Trees
An AVL Tree is a self-balancing binary search tree. The heights of the two child subtrees of any node differ by at most one.
Balance Factor (BF) = Height(Left Subtree) - Height(Right Subtree)
For an AVL tree, BF must be -1, 0, or 1 for every node.
Rotations for Balancing
To restore balance after insertion or deletion, four types of rotations are used:
- LL (Left-Left): Single right rotation.
- RR (Right-Right): Single left rotation.
- LR (Left-Right): Left rotation followed by right rotation.
- RL (Right-Left): Right rotation followed by left rotation.
6. Heap Tree
A Heap is a specialized complete binary tree that satisfies the heap property:
- Max Heap: The key of the root node is greater than or equal to the keys of its children.
- Min Heap: The key of the root node is less than or equal to the keys of its children.
Common Mistakes
- Mistaking a Binary Tree for a Binary Search Tree. Remember: A Binary Tree has no specific ordering rule like the BST.
- Forgetting to update the Balance Factor (BF) of all ancestors after an AVL insertion.
Frequently Asked Questions
Q: What is the time complexity of searching in a BST?
Average case: O(log n). Worst case (skewed tree): O(n). This is why balanced trees like AVL are used.
Q: Why use Threaded Binary Trees?
They make it easier to find the in-order successor/predecessor without extra memory for a stack during traversal.