Trees

Trees

Trees are hierarchical data structures widely used in computer science. Understanding trees is crucial for GATE CS.

Tree Basics

Tree is a connected acyclic graph with n nodes and n-1 edges.

Tree Terminology

• Node: Element in tree
• Root: Topmost node
• Parent: Node with children
• Child: Node below parent
• Leaf: Node with no children
• Sibling: Nodes with same parent
• Ancestor: Node on path from root
• Descendant: Node below current node
• Depth: Distance from root
• Height: Maximum depth
• Level: Nodes at same depth

Tree Properties

• Number of nodes: n
• Number of edges: n - 1
• Number of leaves: Can vary
• Height: h (0 to n-1)
• Maximum nodes at level i: 2^i (for binary tree)

Binary Tree

Binary Tree is a tree where each node has at most 2 children (left and right).

Binary Tree Properties

• Maximum nodes in tree of height h: 2^(h+1) - 1
• Minimum height with n nodes: ⌈log₂(n+1)⌉ - 1
• Maximum height with n nodes: n - 1
• Number of leaf nodes: At least 1, at most ⌈n/2⌉

Binary Tree Types

1. Full Binary Tree

Every node has 0 or 2 children.

Properties:

• Number of leaves = Number of internal nodes + 1

2. Complete Binary Tree

All levels filled except possibly last, filled left to right.

Properties:

• Height = ⌊log₂ n⌋
• Can be stored in array efficiently

3. Perfect Binary Tree

All levels completely filled.

Properties:

• Number of nodes = 2^(h+1) - 1
• Number of leaves = 2^h

Tree Traversals

1. Inorder Traversal (Left-Root-Right)

Algorithm:

1. Traverse left subtree
2. Visit root
3. Traverse right subtree

Code:

void inorder(Node* root) {
    if (root != NULL) {
        inorder(root->left);
        printf("%d ", root->data);
        inorder(root->right);
    }
}

Time Complexity: O(n)

Space Complexity: O(h) where h is height

Result: For BST, gives sorted order

2. Preorder Traversal (Root-Left-Right)

Algorithm:

1. Visit root
2. Traverse left subtree
3. Traverse right subtree

Code:

void preorder(Node* root) {
    if (root != NULL) {
        printf("%d ", root->data);
        preorder(root->left);
        preorder(root->right);
    }
}

Application: Create copy of tree, get prefix expression

3. Postorder Traversal (Left-Right-Root)

Algorithm:

1. Traverse left subtree
2. Traverse right subtree
3. Visit root

Code:

void postorder(Node* root) {
    if (root != NULL) {
        postorder(root->left);
        postorder(root->right);
        printf("%d ", root->data);
    }
}

Application: Delete tree, get postfix expression

4. Level Order Traversal

Algorithm:

Use queue to visit nodes level by level.

Code:

void levelOrder(Node* root) {
    if (root == NULL) return;
    
    Queue q;
    enqueue(&q, root);
    
    while (!isEmpty(&q)) {
        Node* node = dequeue(&q);
        printf("%d ", node->data);
        
        if (node->left != NULL)
            enqueue(&q, node->left);
        if (node->right != NULL)
            enqueue(&q, node->right);
    }
}

Time Complexity: O(n)

Space Complexity: O(w) where w is maximum width

Binary Search Tree (BST)

BST is a binary tree where:

• Left subtree < Root < Right subtree
• This property holds recursively

BST Operations

Search

Algorithm:

1. Start from root
2. If key == root, found
3. If key < root, search left subtree
4. If key > root, search right subtree

Code:

Node* search(Node* root, int key) {
    if (root == NULL || root->data == key)
        return root;
    
    if (key < root->data)
        return search(root->left, key);
    else
        return search(root->right, key);
}

Time Complexity: O(h) where h is height

• Best case: O(log n) for balanced tree
• Worst case: O(n) for skewed tree

Insert

Algorithm:

1. Find appropriate position
2. Insert as leaf node

Code:

Node* insert(Node* root, int key) {
    if (root == NULL)
        return createNode(key);
    
    if (key < root->data)
        root->left = insert(root->left, key);
    else if (key > root->data)
        root->right = insert(root->right, key);
    
    return root;
}

Time Complexity: O(h)

Delete

Three Cases:

1. Leaf node: Simply delete
2. One child: Replace with child
3. Two children: Replace with inorder successor/predecessor

Code:

Node* delete(Node* root, int key) {
    if (root == NULL) return root;
    
    if (key < root->data)
        root->left = delete(root->left, key);
    else if (key > root->data)
        root->right = delete(root->right, key);
    else {
        // Node to delete found
        if (root->left == NULL) {
            Node* temp = root->right;
            free(root);
            return temp;
        } else if (root->right == NULL) {
            Node* temp = root->left;
            free(root);
            return temp;
        }
        
        // Two children: get inorder successor
        Node* temp = minValueNode(root->right);
        root->data = temp->data;
        root->right = delete(root->right, temp->data);
    }
    return root;
}

Time Complexity: O(h)

BST Properties

• Inorder traversal gives sorted sequence
• Minimum value: Leftmost node
• Maximum value: Rightmost node
• Successor: Smallest value greater than node
• Predecessor: Largest value smaller than node

AVL Tree

AVL Tree is a self-balancing BST where:

• Height difference between left and right subtrees ≤ 1
• Balance factor = Height(left) - Height(right)

Rotations

1. Right Rotation (LL Case)

When: Left subtree is taller

Operation:

• Make left child the new root
• Original root becomes right child of new root

2. Left Rotation (RR Case)

When: Right subtree is taller

Operation:

• Make right child the new root
• Original root becomes left child of new root

3. Left-Right Rotation (LR Case)

When: Left child's right subtree is taller

Operation:

• Left rotate left child
• Right rotate root

4. Right-Left Rotation (RL Case)

When: Right child's left subtree is taller

Operation:

• Right rotate right child
• Left rotate root

AVL Tree Operations

All operations: O(log n) guaranteed

Insert/Delete: May require rotations to maintain balance

GATE CS Important Points

1. Tree Properties: Know all formulas and properties
2. Traversals: Master all four traversal methods
3. BST Operations: Search, insert, delete complexities
4. Tree Construction: Build tree from traversals
5. AVL Rotations: Understand all rotation types

Practice Tips

1. Implement Traversals: Code all traversal methods
2. BST Operations: Practice search, insert, delete
3. Tree Construction: Build tree from given traversals
4. Height Calculation: Practice height/depth problems
5. Previous Year Questions: Solve GATE tree questions