Unit III: Trees

Table of Contents

1. Introduction to Trees
2. Binary Search Trees (BST)
3. Tree Traversals
4. Threaded Binary Trees
5. Height-Balanced (AVL) Trees
6. Heap 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.