Trees, binary search trees, AVL trees and heaps notes — Unit 4

Unlike arrays, linked lists, stacks, and queues which are linear, a Tree is a hierarchical (non-linear) data structure. It consists of nodes connected by edges.

⇒1.1 Basic Terminology

• Root: The topmost node of the tree. It has no parent.
• Edge: The connecting link between two nodes.
• Parent & Child: A node that has branches leading to other nodes is a parent. The nodes it connects to are its children.
• Leaf (External) Node: A node with no children (degree zero).
• Internal Node: A node with at least one child.
• Siblings: Nodes that share the same parent.
• Depth of a Node: Number of edges from the root to that node.
• Height of a Tree: Number of edges on the longest path from the root to a leaf.

A Binary Tree is a special type of tree in which every node can have a maximum of two children, typically distinguished as the left child and the right child.

⇒2.1 Types of Binary Trees

• Full (Strict) Binary Tree: Every node has either 0 or 2 children. No node has exactly 1 child.
• Perfect Binary Tree: All internal nodes have 2 children, and all leaf nodes are at the same level.
• Complete Binary Tree: All levels are completely filled except possibly the last level, and the last level has all keys as left as possible.
• Degenerate (Pathological) Tree: Every internal node has exactly one child. It essentially behaves like a linked list.

⇒2.2 Properties

• The maximum number of nodes at level $l$ is $2^l$ (where root is level 0).
• Maximum nodes in a tree of height $h$ is $2^{h+1} - 1$.
• For a tree with $N$ nodes, minimum height is $\lfloor \log_2 N \rfloor$.

Binary trees can be represented in memory using arrays or linked structures.

⇒3.1 Array Representation

Used primarily for Complete Binary Trees (like Heaps). If a node is at index $i$:

• Left child is at $2i + 1$
• Right child is at $2i + 2$
• Parent is at $\lfloor(i - 1) / 2\rfloor$

Drawback: Wastes massive amounts of memory for skewed or sparse trees.

⇒3.2 Linked Representation

The standard and most flexible way. Each node contains a data field and two pointer fields.

```c
struct TreeNode {
int data;
struct TreeNode left; struct TreeNode right;
};
```

Traversal is the process of visiting all nodes of a tree. Since trees are non-linear, there is no single sequence to visit them. Depth First Search (DFS) style traversals are typically implemented using Recursion.

⇒4.1 Inorder Traversal (Left, Root, Right)

1. Traverse Left Subtree
2. Visit Root
3. Traverse Right Subtree

(Note: In a Binary Search Tree, Inorder traversal yields elements in sorted, ascending order).

⇒4.2 Preorder Traversal (Root, Left, Right)

1. Visit Root
2. Traverse Left Subtree
3. Traverse Right Subtree

(Used to create a copy of the tree).

⇒4.3 Postorder Traversal (Left, Right, Root)

1. Traverse Left Subtree
2. Traverse Right Subtree
3. Visit Root

(Used to delete a tree, as you must delete children before the parent).

Instead of going deep, Breadth First Search (BFS) or Level Order Traversal visits nodes level by level, from top to bottom, left to right.

⇒5.1 Implementation using a Queue

BFS requires a Queue data structure to keep track of nodes to visit.

• Enqueue the Root node.
• Loop while the Queue is not empty:
• - Dequeue a node and print its data.
• - If the node has a left child, enqueue it.
• - If the node has a right child, enqueue it.

Time Complexity: $O(n)$, since every node is enqueued and dequeued exactly once.
Space Complexity: $O(w)$, where $w$ is the maximum width of the tree (number of nodes at the widest level).

A Binary Search Tree is a node-based binary tree data structure with the following properties:

• The left subtree of a node contains only nodes with keys lesser than the node’s key.
• The right subtree of a node contains only nodes with keys greater than the node’s key.
• The left and right subtrees must also be binary search trees.
• There must be no duplicate nodes (usually).

⇒6.1 Why BST?

A BST combines the flexibility of insertion/deletion in Linked Lists with the efficiency of Binary Search in Arrays. On average, it provides $O(\log n)$ time complexity for Search, Insert, and Delete operations.

⇒7.1 Searching in a BST

• Compare the key with the root.
• If key equals root, return true.
• If key is less than root, search recursively in the left subtree.
• If key is greater than root, search recursively in the right subtree.

⇒7.2 Insertion in a BST

A new key is always inserted as a leaf node. We trace the path from the root down to a leaf just like searching, and attach the new node where the search falls off the tree.

```c
struct Node insert(struct Node node, int key) {
if (node == NULL) return newNode(key);
if (key < node->data)
node->left = insert(node->left, key);
else if (key > node->data)
node->right = insert(node->right, key);
return node;
}
```

Deleting a node is the most complex operation in a BST because the tree must maintain its properties after deletion.

⇒8.1 Three Cases of Deletion

• Case 1: Node to be deleted is a leaf. Simply remove the node and update its parent's pointer to NULL.
• Case 2: Node has only one child. Copy the child to the node and delete the child (effectively bypassing the node).
• Case 3: Node has two children. This is tricky. Find the Inorder Successor of the node. The inorder successor is the smallest node in the right subtree. Copy the successor's data to the target node, then recursively delete the inorder successor (which will fall into Case 1 or 2).

⇒8.2 Time Complexity

Worst-case Time Complexity for all operations (Search, Insert, Delete) is $O(h)$ where $h$ is the height of the tree. In an unbalanced (skewed) tree, this degrades to $O(n)$.

The major flaw of a standard BST is that if elements are inserted in sorted order, it degenerates into a linked list, degrading search time to $O(n)$.

An AVL Tree (named after Adelson-Velsky and Landis) is a self-balancing Binary Search Tree. It ensures the height of the tree remains $O(\log n)$ at all times.

⇒9.1 Balance Factor

In an AVL tree, the heights of the two child subtrees of any node differ by at most one. The Balance Factor (BF) is calculated as:

$BF = Height(Left Subtree) - Height(Right Subtree)$

For a tree to be an AVL tree, the Balance Factor of every node must be $-1$, $0$, or $+1$.

If an insertion or deletion causes the Balance Factor of any node to become $2$ or $-2$, the tree has become unbalanced. We perform Rotations to rebalance it.

⇒10.1 Four Types of Rotations

• LL Rotation (Left-Left Case): Inserted node is in the left subtree of the left child. Solution: Single Right Rotation.
• RR Rotation (Right-Right Case): Inserted node is in the right subtree of the right child. Solution: Single Left Rotation.
• LR Rotation (Left-Right Case): Inserted node is in the right subtree of the left child. Solution: Left Rotation on child, then Right Rotation on parent.
• RL Rotation (Right-Left Case): Inserted node is in the left subtree of the right child. Solution: Right Rotation on child, then Left Rotation on parent.

Rotations take $O(1)$ time, guaranteeing that overall insertion/deletion in an AVL tree remains strictly $O(\log n)$.

A Heap is a special Tree-based data structure that satisfies the Heap Property. It must be a Complete Binary Tree.

⇒11.1 Types of Heaps

• Max-Heap: The key present at the root node must be greatest among the keys present at all of its children. This property must be recursively true for all subtrees.
• Min-Heap: The key present at the root node must be minimum among the keys present at all of its children. This property is recursively true for all subtrees.

⇒11.2 Array Representation of Heaps

Because a Heap is a Complete Binary Tree, it is almost exclusively implemented using an Array. This avoids pointer overhead and is highly cache-efficient.

⇒12.1 Insertion in a Heap

• Insert the new element at the very end of the array (to maintain the Complete Binary Tree property).
• Heapify Up: Compare the new element with its parent. If it violates the heap property (e.g., larger than parent in a Max-Heap), swap them. Repeat until the property is satisfied or the root is reached.

Time Complexity: $O(\log n)$

⇒12.2 Deletion (Extract-Max / Extract-Min)

• You can only extract the root element from a Heap.
• Replace the root with the last element in the array.
• Remove the last element.
• Heapify Down: Compare the new root with its children. Swap with the larger child (in Max-Heap). Repeat until the property is restored.

Time Complexity: $O(\log n)$

Given an unsorted array, how do we convert it into a Heap?

⇒13.1 Approach 1: Successive Insertions

Start with an empty heap and insert elements one by one.
Time Complexity: $n$ insertions $\times O(\log n)$ per insertion = $O(n \log n)$.

⇒13.2 Approach 2: Floyd’s Build-Heap Algorithm

This is a bottom-up approach that is mathematically proven to run in $O(n)$ time.

• Treat the array as a complete binary tree.
• Leaf nodes trivially satisfy the heap property on their own.
• Start from the last non-leaf node (index $n/2 - 1$) and move backwards to the root (index 0).
• Call `Heapify-Down` on each of these nodes.

The $O(n)$ complexity arises because most nodes are at the bottom of the tree, where `Heapify-Down` only takes $O(1)$ or $O(2)$ steps.

Trees form the basis of advanced computer science topics. Ensure you understand the following.

⇒14.1 University Exam Checklist

• Define Complete, Perfect, and Strict Binary Trees.
• Write C recursive functions for Inorder, Preorder, and Postorder traversals.
• Construct a BST from a given sequence of numbers.
• Explain the three cases of node deletion in a BST.
• Define an AVL tree and its Balance Factor. Demonstrate LL and LR rotations with an example.
• Explain the array representation of a Max-Heap.

⇒14.2 Placement Interview Focus

• Find the Lowest Common Ancestor (LCA) of two nodes in a BST and a Binary Tree.
• Check if a given Binary Tree is a valid BST.
• Write code for Level Order Traversal (BFS) using a Queue.
• Find the Maximum Depth/Height of a binary tree.
• Invert a Binary Tree (Mirror image).