Trees

Introduction to Trees

A tree is a hierarchical data structure that consists of nodes connected by edges. Unlike linear data structures such as arrays, linked lists, stacks, and queues, which have a sequential relationship between elements, trees have a hierarchical relationship between elements.

Trees are widely used in various applications such as representing hierarchical data, organizing data for quick search, insertion, and deletion, and implementing efficient algorithms for various computational problems.

            ┌───┐
            │ A │
            └─┬─┘
              │
      ┌───────┴───────┐
      │               │
    ┌─┴─┐           ┌─┴─┐
    │ B │           │ C │
    └─┬─┘           └─┬─┘
      │               │
┌─────┴─────┐     ┌───┴───┐
│           │     │       │
┌┴┐       ┌─┴─┐ ┌─┴─┐   ┌─┴─┐
│D│       │ E │ │ F │   │ G │
└─┘       └───┘ └───┘   └───┘
                        

Key Terminology

• Node: Each element in a tree is called a node. In the above example, A, B, C, D, E, F, and G are nodes.
• Root: The topmost node of a tree is called the root. In the above example, A is the root.
• Parent: A node that has one or more child nodes. In the above example, A is the parent of B and C, B is the parent of D and E, and C is the parent of F and G.
• Child: A node that has a parent node. In the above example, B and C are children of A, D and E are children of B, and F and G are children of C.
• Siblings: Nodes that share the same parent are called siblings. In the above example, B and C are siblings, D and E are siblings, and F and G are siblings.
• Leaf: A node that has no children is called a leaf node. In the above example, D, E, F, and G are leaf nodes.
• Internal Node: A node that has at least one child is called an internal node. In the above example, A, B, and C are internal nodes.
• Edge: The connection between two nodes is called an edge. In the above example, the lines connecting the nodes are edges.
• Path: A sequence of nodes and edges connecting two nodes. For example, the path from A to E is A-B-E.
• Depth: The depth of a node is the number of edges from the root to the node. In the above example, the depth of A is 0, the depth of B and C is 1, and the depth of D, E, F, and G is 2.
• Height: The height of a node is the number of edges on the longest path from the node to a leaf. In the above example, the height of A is 2, the height of B and C is 1, and the height of D, E, F, and G is 0.
• Level: The level of a node is defined as (depth of the node + 1). In the above example, A is at level 1, B and C are at level 2, and D, E, F, and G are at level 3.
• Degree: The degree of a node is the number of children it has. In the above example, the degree of A is 2, the degree of B is 2, the degree of C is 2, and the degree of D, E, F, and G is 0.
• Forest: A collection of disjoint trees is called a forest.

Representation of a General Tree

A general tree is a tree where each node can have an arbitrary number of children. There are several ways to represent a general tree:

1. List Representation

In this representation, each node contains a data field and a list of references to its children.

struct Node {
    int data;
    vector children;
};
                    

2. First Child - Next Sibling Representation

In this representation, each node contains a data field, a reference to its first child, and a reference to its next sibling.

struct Node {
    int data;
    Node* firstChild;
    Node* nextSibling;
};
                    

            ┌───┐
            │ A │
            └─┬─┘
              │
              ▼
            ┌───┐       ┌───┐
            │ B │──────>│ C │──────> NULL
            └─┬─┘       └─┬─┘
              │           │
              ▼           ▼
            ┌───┐       ┌───┐       ┌───┐
            │ D │──────>│ E │──────>│ F │──────>│ G │──────> NULL
            └───┘       └───┘       └───┘       └───┘
                        

3. Array Representation

In this representation, the tree is stored in an array. For a node at index i:

• Its parent is at index (i-1)/n, where n is the maximum number of children a node can have.
• Its j-th child is at index n*i + j, where 1 ≤ j ≤ n.

This representation is efficient for complete trees but can waste space for sparse trees.

Binary Tree Introduction

A binary tree is a tree data structure in which each node has at most two children, referred to as the left child and the right child.

            ┌───┐
            │ A │
            └─┬─┘
              │
      ┌───────┴───────┐
      │               │
    ┌─┴─┐           ┌─┴─┐
    │ B │           │ C │
    └─┬─┘           └─┬─┘
      │               │
┌─────┴─────┐         │
│           │         │
┌┴┐       ┌─┴─┐     ┌─┴─┐
│D│       │ E │     │ F │
└─┘       └───┘     └───┘
                        

Types of Binary Trees

• Full Binary Tree: A binary tree in which every node has either 0 or 2 children.
• Complete Binary Tree: A binary tree in which all levels are completely filled except possibly the last level, which is filled from left to right.
• Perfect Binary Tree: A binary tree in which all internal nodes have exactly two children and all leaf nodes are at the same level.
• Balanced Binary Tree: A binary tree in which the height of the left and right subtrees of any node differ by at most one.
• Degenerate (or Pathological) Binary Tree: A binary tree in which each parent node has only one child, effectively becoming a linked list.

Full Binary Tree:       Complete Binary Tree:    Perfect Binary Tree:

      ┌───┐                  ┌───┐                    ┌───┐
      │ A │                  │ A │                    │ A │
      └─┬─┘                  └─┬─┘                    └─┬─┘
        │                      │                        │
  ┌─────┴─────┐        ┌─────┴─────┐            ┌─────┴─────┐
  │           │        │           │            │           │
┌─┴─┐       ┌─┴─┐    ┌─┴─┐       ┌─┴─┐        ┌─┴─┐       ┌─┴─┐
│ B │       │ C │    │ B │       │ C │        │ B │       │ C │
└─┬─┘       └─┬─┘    └─┬─┘       └─┬─┘        └─┬─┘       └─┬─┘
  │           │        │           │            │           │
┌─┴─┐       ┌─┴─┐    ┌─┴─┐       ┌─┴─┐      ┌───┴───┐   ┌───┴───┐
│ D │       │ E │    │ D │       │ E │      │       │   │       │
└───┘       └───┘    └─┬─┘       └───┘    ┌─┴─┐   ┌─┴─┐ ┌─┴─┐ ┌─┴─┐
                       │                  │ D │   │ E │ │ F │ │ G │
                     ┌─┴─┐                └───┘   └───┘ └───┘ └───┘
                     │ F │
                     └───┘

Balanced Binary Tree:   Degenerate Binary Tree:

      ┌───┐                  ┌───┐
      │ A │                  │ A │
      └─┬─┘                  └─┬─┘
        │                      │
  ┌─────┴─────┐                │
  │           │                │
┌─┴─┐       ┌─┴─┐            ┌─┴─┐
│ B │       │ C │            │ B │
└─┬─┘       └───┘            └─┬─┘
  │                            │
┌─┴─┐                        ┌─┴─┐
│ D │                        │ C │
└───┘                        └───┘
                        

Binary Tree Abstract Data Type

A binary tree is an abstract data type (ADT) that specifies a collection of elements with specific operations but does not specify how these operations are implemented. The ADT defines what operations are allowed on the data structure, but not how these operations are implemented.

Binary Tree ADT Specification

The Binary Tree ADT can be defined as follows:

ADT BinaryTree {
    // Data
    A collection of elements arranged in a hierarchical structure
    
    // Operations
    void insert(element)                // Insert an element into the binary tree
    void delete(element)                // Delete an element from the binary tree
    bool search(element)                // Search for an element in the binary tree
    void traversePreorder()             // Traverse the binary tree in preorder
    void traverseInorder()              // Traverse the binary tree in inorder
    void traversePostorder()            // Traverse the binary tree in postorder
    int height()                        // Return the height of the binary tree
    int size()                          // Return the number of nodes in the binary tree
    bool isEmpty()                      // Check if the binary tree is empty
}
                    

This ADT specification defines what a binary tree is and what operations it supports, but it does not specify how these operations are implemented. The implementation can vary depending on the specific requirements and constraints.

Implementation of Binary Trees

Binary trees can be implemented using various data structures. Let's explore some common implementations:

1. Linked Representation

In the linked representation, each node contains a data field and two references (links): one to the left child and one to the right child.

#include <iostream>
using namespace std;

// Node structure for binary tree
struct Node {
    int data;
    Node* left;
    Node* right;
    
    // Constructor
    Node(int val) {
        data = val;
        left = right = NULL;
    }
};

// Binary Tree class
class BinaryTree {
private:
    Node* root;
    
    // Helper function for inserting a node
    Node* insertNode(Node* node, int val) {
        // If the tree is empty, create a new node
        if (node == NULL) {
            return new Node(val);
        }
        
        // Otherwise, recur down the tree
        if (val < node->data) {
            node->left = insertNode(node->left, val);
        } else if (val > node->data) {
            node->right = insertNode(node->right, val);
        }
        
        // Return the unchanged node pointer
        return node;
    }
    
    // Helper function for searching a node
    bool searchNode(Node* node, int val) {
        // Base case: If the tree is empty or the value is found
        if (node == NULL) {
            return false;
        }
        if (node->data == val) {
            return true;
        }
        
        // Recur down the tree
        if (val < node->data) {
            return searchNode(node->left, val);
        } else {
            return searchNode(node->right, val);
        }
    }
    
    // Helper function for preorder traversal
    void preorderTraversal(Node* node) {
        if (node == NULL) {
            return;
        }
        
        // Visit the root
        cout << node->data << " ";
        
        // Traverse the left subtree
        preorderTraversal(node->left);
        
        // Traverse the right subtree
        preorderTraversal(node->right);
    }
    
    // Helper function for inorder traversal
    void inorderTraversal(Node* node) {
        if (node == NULL) {
            return;
        }
        
        // Traverse the left subtree
        inorderTraversal(node->left);
        
        // Visit the root
        cout << node->data << " ";
        
        // Traverse the right subtree
        inorderTraversal(node->right);
    }
    
    // Helper function for postorder traversal
    void postorderTraversal(Node* node) {
        if (node == NULL) {
            return;
        }
        
        // Traverse the left subtree
        postorderTraversal(node->left);
        
        // Traverse the right subtree
        postorderTraversal(node->right);
        
        // Visit the root
        cout << node->data << " ";
    }
    
    // Helper function for calculating the height of the tree
    int calculateHeight(Node* node) {
        if (node == NULL) {
            return -1;
        }
        
        int leftHeight = calculateHeight(node->left);
        int rightHeight = calculateHeight(node->right);
        
        return max(leftHeight, rightHeight) + 1;
    }
    
    // Helper function for calculating the size of the tree
    int calculateSize(Node* node) {
        if (node == NULL) {
            return 0;
        }
        
        return calculateSize(node->left) + calculateSize(node->right) + 1;
    }
    
public:
    // Constructor
    BinaryTree() {
        root = NULL;
    }
    
    // Insert a value into the binary tree
    void insert(int val) {
        root = insertNode(root, val);
    }
    
    // Search for a value in the binary tree
    bool search(int val) {
        return searchNode(root, val);
    }
    
    // Preorder traversal of the binary tree
    void traversePreorder() {
        cout << "Preorder traversal: ";
        preorderTraversal(root);
        cout << endl;
    }
    
    // Inorder traversal of the binary tree
    void traverseInorder() {
        cout << "Inorder traversal: ";
        inorderTraversal(root);
        cout << endl;
    }
    
    // Postorder traversal of the binary tree
    void traversePostorder() {
        cout << "Postorder traversal: ";
        postorderTraversal(root);
        cout << endl;
    }
    
    // Get the height of the binary tree
    int height() {
        return calculateHeight(root);
    }
    
    // Get the size of the binary tree
    int size() {
        return calculateSize(root);
    }
    
    // Check if the binary tree is empty
    bool isEmpty() {
        return root == NULL;
    }
};

int main() {
    BinaryTree tree;
    
    // Insert nodes
    tree.insert(50);
    tree.insert(30);
    tree.insert(70);
    tree.insert(20);
    tree.insert(40);
    tree.insert(60);
    tree.insert(80);
    
    // Traverse the tree
    tree.traversePreorder();
    tree.traverseInorder();
    tree.traversePostorder();
    
    // Search for values
    cout << "Search for 40: " << (tree.search(40) ? "Found" : "Not Found") << endl;
    cout << "Search for 90: " << (tree.search(90) ? "Found" : "Not Found") << endl;
    
    // Get height and size
    cout << "Height of the tree: " << tree.height() << endl;
    cout << "Size of the tree: " << tree.size() << endl;
    
    return 0;
}
                    

2. Array Representation

In the array representation, the binary tree is stored in an array. For a node at index i:

• Its left child is at index 2*i + 1
• Its right child is at index 2*i + 2
• Its parent is at index (i-1)/2

This representation is efficient for complete binary trees but can waste space for sparse trees.

#include <iostream>
#include <vector>
using namespace std;

class BinaryTree {
private:
    vector arr;
    
    // Helper function to check if a node exists
    bool isNodeExists(int index) {
        return index < arr.size() && arr[index] != -1;
    }
    
public:
    // Constructor
    BinaryTree(int size) {
        arr.resize(size, -1);  // Initialize with -1 (indicating empty node)
    }
    
    // Insert a value at a specific index
    void insert(int index, int val) {
        if (index >= arr.size()) {
            cout << "Index out of bounds" << endl;
            return;
        }
        
        arr[index] = val;
    }
    
    // Get the value at a specific index
    int get(int index) {
        if (index >= arr.size() || arr[index] == -1) {
            cout << "Node does not exist" << endl;
            return -1;
        }
        
        return arr[index];
    }
    
    // Get the left child of a node
    int getLeftChild(int index) {
        int leftChildIndex = 2 * index + 1;
        
        if (!isNodeExists(leftChildIndex)) {
            cout << "Left child does not exist" << endl;
            return -1;
        }
        
        return arr[leftChildIndex];
    }
    
    // Get the right child of a node
    int getRightChild(int index) {
        int rightChildIndex = 2 * index + 2;
        
        if (!isNodeExists(rightChildIndex)) {
            cout << "Right child does not exist" << endl;
            return -1;
        }
        
        return arr[rightChildIndex];
    }
    
    // Get the parent of a node
    int getParent(int index) {
        if (index <= 0 || index >= arr.size()) {
            cout << "Invalid index or root node" << endl;
            return -1;
        }
        
        int parentIndex = (index - 1) / 2;
        
        if (!isNodeExists(parentIndex)) {
            cout << "Parent does not exist" << endl;
            return -1;
        }
        
        return arr[parentIndex];
    }
    
    // Preorder traversal
    void preorderTraversal(int index) {
        if (!isNodeExists(index)) {
            return;
        }
        
        cout << arr[index] << " ";
        preorderTraversal(2 * index + 1);
        preorderTraversal(2 * index + 2);
    }
    
    // Inorder traversal
    void inorderTraversal(int index) {
        if (!isNodeExists(index)) {
            return;
        }
        
        inorderTraversal(2 * index + 1);
        cout << arr[index] << " ";
        inorderTraversal(2 * index + 2);
    }
    
    // Postorder traversal
    void postorderTraversal(int index) {
        if (!isNodeExists(index)) {
            return;
        }
        
        postorderTraversal(2 * index + 1);
        postorderTraversal(2 * index + 2);
        cout << arr[index] << " ";
    }
    
    // Print the tree
    void printTree() {
        cout << "Array representation of the tree: ";
        for (int i = 0; i < arr.size(); i++) {
            if (arr[i] != -1) {
                cout << arr[i] << " ";
            } else {
                cout << "- ";
            }
        }
        cout << endl;
    }
};

int main() {
    BinaryTree tree(10);
    
    // Insert nodes
    tree.insert(0, 50);  // Root
    tree.insert(1, 30);  // Left child of root
    tree.insert(2, 70);  // Right child of root
    tree.insert(3, 20);  // Left child of 30
    tree.insert(4, 40);  // Right child of 30
    tree.insert(5, 60);  // Left child of 70
    tree.insert(6, 80);  // Right child of 70
    
    // Print the tree
    tree.printTree();
    
    // Traverse the tree
    cout << "Preorder traversal: ";
    tree.preorderTraversal(0);
    cout << endl;
    
    cout << "Inorder traversal: ";
    tree.inorderTraversal(0);
    cout << endl;
    
    cout << "Postorder traversal: ";
    tree.postorderTraversal(0);
    cout << endl;
    
    // Get children and parent
    cout << "Left child of root: " << tree.getLeftChild(0) << endl;
    cout << "Right child of root: " << tree.getRightChild(0) << endl;
    cout << "Parent of node at index 3: " << tree.getParent(3) << endl;
    
    return 0;
}
                    

Binary Tree Traversals

Tree traversal is the process of visiting each node in a tree exactly once. There are several ways to traverse a binary tree:

1. Preorder Traversal

In preorder traversal, the root node is visited first, then the left subtree, and finally the right subtree.

Algorithm:

1. Visit the root.
2. Traverse the left subtree in preorder.
3. Traverse the right subtree in preorder.

            ┌───┐
            │ A │ ← 1
            └─┬─┘
              │
      ┌───────┴───────┐
      │               │
    ┌─┴─┐           ┌─┴─┐
    │ B │ ← 2       │ C │ ← 4
    └─┬─┘           └─┬─┘
      │               │
┌─────┴─────┐         │
│           │         │
┌┴┐       ┌─┴─┐     ┌─┴─┐
│D│ ← 3   │ E │ ← 4 │ F │ ← 6
└─┘       └───┘     └───┘

Preorder Traversal: A B D E C F
                        

2. Inorder Traversal

In inorder traversal, the left subtree is visited first, then the root node, and finally the right subtree.

Algorithm:

1. Traverse the left subtree in inorder.
2. Visit the root.
3. Traverse the right subtree in inorder.

            ┌───┐
            │ A │ ← 3
            └─┬─┘
              │
      ┌───────┴───────┐
      │               │
    ┌─┴─┐           ┌─┴─┐
    │ B │ ← 2       │ C │ ← 5
    └─┬─┘           └─┬─┘
      │               │
┌─────┴─────┐         │
│           │         │
┌┴┐       ┌─┴─┐     ┌─┴─┐
│D│ ← 1   │ E │ ← 3 │ F │ ← 6
└─┘       └───┘     └───┘

Inorder Traversal: D B E A C F
                        

3. Postorder Traversal

In postorder traversal, the left subtree is visited first, then the right subtree, and finally the root node.

Algorithm:

1. Traverse the left subtree in postorder.
2. Traverse the right subtree in postorder.
3. Visit the root.

            ┌───┐
            │ A │ ← 6
            └─┬─┘
              │
      ┌───────┴───────┐
      │               │
    ┌─┴─┐           ┌─┴─┐
    │ B │ ← 3       │ C │ ← 5
    └─┬─┘           └─┬─┘
      │               │
┌─────┴─────┐         │
│           │         │
┌┴┐       ┌─┴─┐     ┌─┴─┐
│D│ ← 1   │ E │ ← 2 │ F │ ← 4
└─┘       └───┘     └───┘

Postorder Traversal: D E B F C A
                        

4. Level Order Traversal

In level order traversal, nodes are visited level by level, from left to right.

Algorithm:

1. Create an empty queue and enqueue the root node.
2. While the queue is not empty:
   1. Dequeue a node from the queue and visit it.
   2. Enqueue the left child of the dequeued node if it exists.
   3. Enqueue the right child of the dequeued node if it exists.

            ┌───┐
            │ A │ ← Level 1
            └─┬─┘
              │
      ┌───────┴───────┐
      │               │
    ┌─┴─┐           ┌─┴─┐
    │ B │           │ C │ ← Level 2
    └─┬─┘           └─┬─┘
      │               │
┌─────┴─────┐         │
│           │         │
┌┴┐       ┌─┴─┐     ┌─┴─┐
│D│       │ E │     │ F │ ← Level 3
└─┘       └───┘     └───┘

Level Order Traversal: A B C D E F
                        

Here's a C++ implementation of level order traversal:

#include <iostream>
#include <queue>
using namespace std;

// Node structure for binary tree
struct Node {
    int data;
    Node* left;
    Node* right;
    
    // Constructor
    Node(int val) {
        data = val;
        left = right = NULL;
    }
};

// Function for level order traversal
void levelOrderTraversal(Node* root) {
    if (root == NULL) {
        return;
    }
    
    // Create a queue for level order traversal
    queue q;
    
    // Enqueue the root
    q.push(root);
    
    while (!q.empty()) {
        // Dequeue a node from the queue
        Node* node = q.front();
        q.pop();
        
        // Print the node's data
        cout << node->data << " ";
        
        // Enqueue the left child
        if (node->left != NULL) {
            q.push(node->left);
        }
        
        // Enqueue the right child
        if (node->right != NULL) {
            q.push(node->right);
        }
    }
}

int main() {
    // Create a binary tree
    Node* root = new Node(1);
    root->left = new Node(2);
    root->right = new Node(3);
    root->left->left = new Node(4);
    root->left->right = new Node(5);
    root->right->left = new Node(6);
    root->right->right = new Node(7);
    
    cout << "Level Order Traversal: ";
    levelOrderTraversal(root);
    cout << endl;
    
    return 0;
}
                    

Applications of Binary Trees

Binary trees have numerous applications in computer science and real-world scenarios. Let's explore some of the most common ones:

1. Binary Search Trees (BST)

A binary search tree is a binary tree where the left child of a node contains a value less than the node's value, and the right child contains a value greater than the node's value. This property makes BSTs efficient for searching, insertion, and deletion operations.

            ┌───┐
            │ 8 │
            └─┬─┘
              │
      ┌───────┴───────┐
      │               │
    ┌─┴─┐           ┌─┴─┐
    │ 3 │           │ 10│
    └─┬─┘           └─┬─┘
      │               │
┌─────┴─────┐         │
│           │         │
┌┴┐       ┌─┴─┐     ┌─┴─┐
│1│       │ 6 │     │ 14│
└─┘       └─┬─┘     └───┘
            │
        ┌───┴───┐
        │       │
      ┌─┴─┐   ┌─┴─┐
      │ 4 │   │ 7 │
      └───┘   └───┘
                        

2. Expression Trees

Expression trees are binary trees used to represent arithmetic expressions. The leaf nodes represent operands, and the internal nodes represent operators.

            ┌───┐
            │ * │
            └─┬─┘
              │
      ┌───────┴───────┐
      │               │
    ┌─┴─┐           ┌─┴─┐
    │ + │           │ - │
    └─┬─┘           └─┬─┘
      │               │
┌─────┴─────┐   ┌─────┴─────┐
│           │   │           │
┌┴┐       ┌─┴─┐ ┌┴┐       ┌─┴─┐
│a│       │ b │ │c│       │ d │
└─┘       └───┘ └─┘       └───┘
                        

3. Huffman Coding Trees

Huffman coding is a lossless data compression algorithm that uses a binary tree to assign variable-length codes to characters based on their frequencies. Characters with higher frequencies get shorter codes.

4. Priority Queues

Binary heaps, which are complete binary trees, are used to implement priority queues. Priority queues are data structures that allow efficient insertion and extraction of the minimum (or maximum) element.

5. Decision Trees

Decision trees are used in machine learning for classification and regression tasks. Each internal node represents a feature, each branch represents a decision rule, and each leaf node represents an outcome.

6. File Systems

Many file systems use tree structures to organize files and directories. Each directory can contain files and subdirectories, forming a hierarchical structure.

7. Network Routing

Binary trees are used in network routing algorithms to efficiently find the shortest path between nodes in a network.

8. Game Trees

In game theory, game trees are used to represent all possible moves and outcomes in a game. Each node represents a state of the game, and each edge represents a possible move.

Summary

In this section, we covered trees, a fundamental data structure in computer science:

• Introduction to trees and their key terminology
• Representation of general trees
• Binary trees and their types
• Binary tree as an Abstract Data Type (ADT)
• Implementation of binary trees using linked representation and array representation
• Binary tree traversals: preorder, inorder, postorder, and level order
• Applications of binary trees in various domains

Trees are versatile data structures with numerous applications in computer science. Understanding trees is essential for solving many algorithmic problems and implementing various features in software applications.