Hierarchical Data Structures: Binary Trees, Binary Search Trees, Heaps, & Hashing

When it comes to data structures, hierarchical data structures play a critical role in organizing and managing complex datasets. Unlike linear data structures such as arrays, linked lists, stacks, and queues, hierarchical data structures allow for more advanced forms of data manipulation, offering efficient solutions for a wide range of problems. In this article, we will discuss several hierarchical data structures, including binary trees, binary search trees (BSTs), binary heaps, and hashing, along with their applications, properties, and real-world examples.

Binary Tree: A Foundational Hierarchical Data Structure

A binary tree is a fundamental data structure in computer science. It is a type of tree data structure where each node has at most two children, which are commonly referred to as the left child and right child. Binary trees are used to represent hierarchical relationships and are particularly useful in situations where data has a parent-child relationship.

Video Credit: Aaron Jack

Binary Tree Representation

A binary tree is represented by a pointer to the topmost node in the tree, also known as the root. If the tree is empty, the value of the root is NULL. Each node in a binary tree contains three essential parts:

Data: The value or data stored in the node.
Pointer to a left child: A reference to the left child of the node.
Pointer to right child: A reference to the right child of the node.

Binary Tree Traversals

Traversing a binary tree means visiting all the nodes in a particular order. Binary tree traversals can be classified into two main types:

Depth-First Traversal:
Inorder Traversal (Left-Root-Right): First, visit the left child, then the root node, and finally the right child. This traversal is used when we want to retrieve data in sorted order.
Preorder Traversal (Root-Left-Right): The root node is visited first, followed by the left child and then the right child.
Postorder Traversal (Left-Right-Root): In this traversal, the left child is visited first, followed by the right child, and finally the root node.
Breadth-First Traversal (Level Order Traversal): In this method, nodes are visited level by level, starting from the root. It is useful for finding the shortest path in unweighted graphs.

Properties of a Binary Tree

Maximum Nodes at Level ‘l’: At any given level ‘l’ in a binary tree, the maximum number of nodes is 2^l.
Maximum Number of Nodes in a Binary Tree: A binary tree with a height of ‘h’ can have a maximum of 2^{{h+1} – 1} nodes.
Height of the Binary Tree: The height is the maximum number of edges from the root to a leaf. The minimum possible height of a binary tree with ‘n’ nodes is {log₂(n+1)} – 1.
Leaf Nodes: The number of leaf nodes in a binary tree is always one more than the number of nodes with two children.

Basic Operations on Binary Trees

Insertion: Adding an element to the tree.
Deletion: Removing an element from the tree.
Searching: Finding a specific element in the tree.
Traversal: Visiting all the nodes of the tree.

Auxiliary Operations

Finding the Height of the Tree: The number of edges on the longest path from the root to a leaf node.
Calculating the Size of the Tree: The total number of nodes in the tree.

Applications of Binary Trees

Huffman Coding Trees: Used in data compression algorithms.
Expression Trees: Widely used in compilers to represent arithmetic expressions.
File Structures: Binary trees are used to represent the hierarchical structure of files and directories.

For example, in web development, the Document Object Model (DOM) is often represented as a binary tree. Each HTML element can be treated as a node, where parent elements contain child elements, forming a hierarchical structure.

Binary Search Tree (BST): Fast Search in Hierarchical Data Structure

A binary search tree (BST) is a specialized form of a binary tree designed to facilitate efficient searching. In a BST, the nodes are arranged in such a way that for each node:

The left subtree contains only nodes with keys less than the node’s key.
The right subtree contains only nodes with keys greater than the node’s key.
Both the left and right subtrees must also be binary search trees.

Video Credit: Spanning Tree

Binary Search Tree Declaration

Here’s a typical structure of a binary search tree in C/C++:

struct BinarySearchTree{
   int data;
   struct BinarySearchTree* left;
   struct BinarySearchTree* right;
};

Primary Operations in BST

Searching: Search for a specific element in the tree. The time complexity is O(h), where ‘h’ is the height of the tree.
Insertion: Insert a new element into the tree in O(h) time.
Deletion: Remove an element from the tree in O(h) time.

Auxiliary Operations

Finding the Minimum or Maximum Element: The minimum element is found by traversing the left subtree, while the maximum is found by traversing the right subtree.
Finding the kth Smallest Element: This involves inorder traversal to retrieve the sorted order of elements.

Balanced vs. Unbalanced BSTs

If a BST is balanced (i.e., the height of the tree is kept minimal), the search, insertion, and deletion operations can be performed in O(log n) time. Self-balancing binary search trees such as AVL trees, Red-Black trees, and Splay trees ensure that the height of the BST remains proportional to O(log n), leading to faster operations.

Applications of Binary Search Trees

BSTs are frequently used in scenarios where dynamic data insertion and deletion are required, such as in:

E-commerce platforms: Products are added and removed constantly, and they must be presented in sorted order for efficient searching.
Databases: BSTs are used in database indexes to enable faster search operations.

Binary Heap: A Complete Binary Tree

A binary heap is another type of binary tree with special properties. It is commonly used to implement priority queues and is the foundation for efficient algorithms such as Dijkstra’s shortest path algorithm and Prim’s minimum spanning tree algorithm.

Properties of a Binary Heap

Complete Tree: A binary heap is a complete binary tree, meaning all levels except possibly the last are completely filled, and the nodes in the last level are as far left as possible.
Heap Property: A binary heap is either a min-heap or a max-heap:
- In a min-heap, the key at the root is the smallest among all the keys in the tree, and this property is recursively true for all nodes.
- In a max-heap, the root contains the largest key, and the same property holds recursively.

Operations on Binary Heaps

Get Minimum (Min-Heap) or Maximum (Max-Heap): Retrieves the minimum or maximum element in constant time O(1).
Extract Minimum/Maximum: Removes the minimum or maximum element in O(log n) time, as it requires rearranging the heap.
Insertion: Adding a new element takes O(log n) time.
Deletion: Deleting an element takes O(log n) time.

Applications of Binary Heaps

Binary heaps are widely used in priority queues where efficient access to the minimum or maximum element is needed. Some key applications include:

Process Scheduling: In operating systems, priority queues are used to schedule processes based on their priority.
Graph Algorithms: Dijkstra’s algorithm for finding the shortest path and Prim’s algorithm for finding a minimum spanning tree using binary heaps for efficient performance.

Hashing: The Fastest Search Technique

Hashing is an efficient technique for storing and retrieving data. While binary search trees provide logarithmic search time, hashing aims to achieve constant time O(1) search operations under average conditions.

Hash Function

A hash function converts input data into a fixed-size integer, which serves as an index to store the data in a hash table. A good hash function should have the following properties:

Deterministic: The same input should always yield the same hash value.
Efficiently Computable: The hash function should be fast to compute.
Uniform Distribution: The output of the hash function should be uniformly distributed across the hash table to minimize collisions.

Hash Table

A hash table is an array that stores data in slots determined by the hash value of the input. When collisions occur (i.e., multiple inputs produce the same hash value), the hash table uses collision resolution techniques such as chaining or open addressing.

Collision Handling Techniques

Chaining: Each slot in the hash table points to a linked list of values that share the same hash index. This technique requires additional memory for the linked lists.
Open Addressing: All elements are stored in the hash table itself. If a collision occurs, the algorithm searches for the next available slot.

Time Complexity of Hashing

Search, Insertion, and Deletion: The average time complexity for these operations is O(1), while the worst-case complexity is O(n) if many collisions occur.

Applications of Hashing

Data Deduplication: Hashing is used to remove duplicates from large datasets efficiently.
Firewalls and Security: Hashing can detect spam or malicious IP addresses by quickly searching through known patterns.
Caching: Web browsers use hashing to store and quickly retrieve frequently visited URLs.

Also Read for Detailed Information: Understanding Hashing: The Key to Fast and Efficient Data Storage and Retrieval

Detailed Examples of Binary Trees, Binary Search Trees (BSTs), Heaps, and Hashing Implementations

1. Binary Tree Implementation

C++ Implementation of a Binary Tree

#include <iostream>
using namespace std;

struct Node {
    int data;
    Node* left;
    Node* right;

    Node(int val) {
        data = val;
        left = right = nullptr;
    }
};

void inorderTraversal(Node* root) {
    if (root == nullptr) return;

    inorderTraversal(root->left);
    cout << root->data << " ";
    inorderTraversal(root->right);
}

int main() {
    Node* root = new Node(10);
    root->left = new Node(20);
    root->right = new Node(30);
    root->left->left = new Node(40);
    root->left->right = new Node(50);
    root->right->left = new Node(60);
    root->right->right = new Node(70);

    cout << "Inorder Traversal of Binary Tree: ";
    inorderTraversal(root);
    cout << endl;

    return 0;
}

Output:

Inorder Traversal of Binary Tree: 40 20 50 10 60 30 70

C Implementation of a Binary Tree

#include <stdio.h>
#include <stdlib.h>

struct Node {
    int data;
    struct Node* left;
    struct Node* right;
};

struct Node* createNode(int data) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    newNode->data = data;
    newNode->left = newNode->right = NULL;
    return newNode;
}

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

int main() {
    struct Node* root = createNode(10);
    root->left = createNode(20);
    root->right = createNode(30);
    root->left->left = createNode(40);
    root->left->right = createNode(50);
    root->right->left = createNode(60);
    root->right->right = createNode(70);

    printf("Inorder Traversal of Binary Tree: ");
    inorderTraversal(root);
    printf("\n");

    return 0;
}

Output:

Inorder Traversal of Binary Tree: 40 20 50 10 60 30 70

C# Implementation of a Binary Tree

using System;

class Node {
    public int data;
    public Node left, right;

    public Node(int item) {
        data = item;
        left = right = null;
    }
}

class BinaryTree {
    Node root;

    void InorderTraversal(Node node) {
        if (node == null)
            return;

        InorderTraversal(node.left);
        Console.Write(node.data + " ");
        InorderTraversal(node.right);
    }

    public static void Main(String[] args) {
        BinaryTree tree = new BinaryTree();

        tree.root = new Node(10);
        tree.root.left = new Node(20);
        tree.root.right = new Node(30);
        tree.root.left.left = new Node(40);
        tree.root.left.right = new Node(50);
        tree.root.right.left = new Node(60);
        tree.root.right.right = new Node(70);

        Console.Write("Inorder Traversal of Binary Tree: ");
        tree.InorderTraversal(tree.root);
        Console.WriteLine();
    }
}

Output:

Inorder Traversal of Binary Tree: 40 20 50 10 60 30 70

Java Implementation of a Binary Tree

class Node {
    int data;
    Node left, right;

    public Node(int item) {
        data = item;
        left = right = null;
    }
}

class BinaryTree {
    Node root;

    void inorderTraversal(Node node) {
        if (node == null)
            return;

        inorderTraversal(node.left);
        System.out.print(node.data + " ");
        inorderTraversal(node.right);
    }

    public static void main(String[] args) {
        BinaryTree tree = new BinaryTree();

        tree.root = new Node(10);
        tree.root.left = new Node(20);
        tree.root.right = new Node(30);
        tree.root.left.left = new Node(40);
        tree.root.left.right = new Node(50);
        tree.root.right.left = new Node(60);
        tree.root.right.right = new Node(70);

        System.out.print("Inorder Traversal of Binary Tree: ");
        tree.inorderTraversal(tree.root);
        System.out.println();
    }
}

Output:

Inorder Traversal of Binary Tree: 40 20 50 10 60 30 70

PHP Implementation of a Binary Tree

<?php
class Node {
    public $data;
    public $left, $right;

    function __construct($item) {
        $this->data = $item;
        $this->left = $this->right = NULL;
    }
}

class BinaryTree {
    public $root;

    function inorderTraversal($node) {
        if ($node == NULL)
            return;

        $this->inorderTraversal($node->left);
        echo $node->data . " ";
        $this->inorderTraversal($node->right);
    }
}

$tree = new BinaryTree();
$tree->root = new Node(10);
$tree->root->left = new Node(20);
$tree->root->right = new Node(30);
$tree->root->left->left = new Node(40);
$tree->root->left->right = new Node(50);
$tree->root->right->left = new Node(60);
$tree->root->right->right = new Node(70);

echo "Inorder Traversal of Binary Tree: ";
$tree->inorderTraversal($tree->root);
echo "\n";
?>

Output:

Inorder Traversal of Binary Tree: 40 20 50 10 60 30 70

Python Implementation of a Binary Tree

class Node:
    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None

def inorderTraversal(root):
    if root:
        inorderTraversal(root.left)
        print(root.data, end=" ")
        inorderTraversal(root.right)

# Driver code
root = Node(10)
root.left = Node(20)
root.right = Node(30)
root.left.left = Node(40)
root.left.right = Node(50)
root.right.left = Node(60)
root.right.right = Node(70)

print("Inorder Traversal of Binary Tree: ", end="")
inorderTraversal(root)
print()

Output:

Inorder Traversal of Binary Tree: 40 20 50 10 60 30 70

2. Binary Search Tree (BST) Implementation

C++ Implementation of a Binary Search Tree

#include <iostream>
using namespace std;

struct Node {
    int data;
    Node* left;
    Node* right;

    Node(int val) {
        data = val;
        left = right = nullptr;
    }
};

Node* insert(Node* root, int key) {
    if (root == nullptr) return new Node(key);

    if (key < root->data)
        root->left = insert(root->left, key);
    else if (key > root->data)
        root->right = insert(root->right, key);

    return root;
}

void inorderTraversal(Node* root) {
    if (root == nullptr) return;

    inorderTraversal(root->left);
    cout << root->data << " ";
    inorderTraversal(root->right);
}

int main() {
    Node* root = nullptr;
    root = insert(root, 50);
    insert(root, 30);
    insert(root, 20);
    insert(root, 40);
    insert(root, 70);
    insert(root, 60);
    insert(root, 80);

    cout << "Inorder Traversal of Binary Search Tree: ";
    inorderTraversal(root);
    cout << endl;

    return 0;
}

Output:

Inorder Traversal of Binary Search Tree: 20 30 40 50 60 70 80

C Implementation of a Binary Search Tree

#include <stdio.h>
#include <stdlib.h>

struct Node {
    int data;
    struct Node* left;
    struct Node* right;
};

struct Node* createNode(int data) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    newNode->data = data;
    newNode->left = newNode->right = NULL;
    return newNode;
}

struct Node* insert(struct 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;
}

void inorderTraversal(struct Node* root) {
    if (root == NULL) return;

    inorderTraversal(root->left);
    printf("%d ", root->data);
    inorderTraversal(root->right);
}

int main() {
    struct Node* root = NULL;
    root = insert(root, 50);
    insert(root, 30);
    insert(root, 20);
    insert(root, 40);
    insert(root, 70);
    insert(root, 60);
    insert(root, 80);

    printf("Inorder Traversal of Binary Search Tree: ");
    inorderTraversal(root);
    printf("\n");

    return 0;
}

Output:

Inorder Traversal of Binary Search Tree: 20 30 40 50 60 70 80

C# Implementation of a Binary Search Tree

using System;

class Node {
    public int data;
    public Node left, right;

    public Node(int item) {
        data = item;
        left = right = null;
    }
}

class BinarySearchTree {
    Node root;

    Node Insert(Node node, int key) {
        if (node == null)
            return new Node(key);

        if (key < node.data)
            node.left = Insert(node.left, key);
        else if (key > node.data)
            node.right = Insert(node.right, key);

        return node;
    }

    void InorderTraversal(Node node) {
        if (node == null)
            return;

        InorderTraversal(node.left);
        Console.Write(node.data + " ");
        InorderTraversal(node.right);
    }

    public static void Main(String[] args) {
        BinarySearchTree tree = new BinarySearchTree();

        tree.root = tree.Insert(tree.root, 50);
        tree.Insert(tree.root, 30);
        tree.Insert(tree.root, 20);
        tree.Insert(tree.root, 40);
        tree.Insert(tree.root, 70);
        tree.Insert(tree.root, 60);
        tree.Insert(tree.root, 80);

        Console.Write("Inorder Traversal of Binary Search Tree: ");
        tree.InorderTraversal(tree.root);
        Console.WriteLine();
    }
}

Output:

Inorder Traversal of Binary Search Tree: 20 30 40 50 60 70 80

Java Implementation of a Binary Search Tree

class Node {
    int data;
    Node left, right;

    public Node(int item) {
        data = item;
        left = right = null;
    }
}

class BinarySearchTree {
    Node root;

    Node insert(Node node, int key) {
        if (node == null)
            return new Node(key);

        if (key < node.data)
            node.left = insert(node.left, key);
        else if (key > node.data)
            node.right = insert(node.right, key);

        return node;
    }

    void inorderTraversal(Node node) {
        if (node == null)
            return;

        inorderTraversal(node.left);
        System.out.print(node.data + " ");
        inorderTraversal(node.right);
    }

    public static void main(String[] args) {
        BinarySearchTree tree = new BinarySearchTree();

        tree.root = tree.insert(tree.root, 50);
        tree.insert(tree.root, 30);
        tree.insert(tree.root, 20);
        tree.insert(tree.root, 40);
        tree.insert(tree.root, 70);
        tree.insert(tree.root, 60);
        tree.insert(tree.root, 80);

        System.out.print("Inorder Traversal of Binary Search Tree: ");
        tree.inorderTraversal(tree.root);
        System.out.println();
    }
}

Output:

Inorder Traversal of Binary Search Tree: 20 30 40 50 60 70 80

PHP Implementation of a Binary Search Tree

<?php
class Node {
    public $data;
    public $left, $right;

    function __construct($item) {
        $this->data = $item;
        $this->left = $this->right = NULL;
    }
}

class BinarySearchTree {
    public $root;

    function insert($node, $key) {
        if ($node == NULL)
            return new Node($key);

        if ($key < $node->data)
            $node->left = $this->insert($node->left, $key);
        else if ($key > $node->data)
            $node->right = $this->insert($node->right, $key);

        return $node;
    }

    function inorderTraversal($node) {
        if ($node == NULL)
            return;

        $this->inorderTraversal($node->left);
        echo $node->data . " ";
        $this->inorderTraversal($node->right);
    }
}

$tree = new BinarySearchTree();
$tree->root = $tree->insert($tree->root, 50);
$tree->insert($tree->root, 30);
$tree->insert($tree->root, 20);
$tree->insert($tree->root, 40);
$tree->insert($tree->root, 70);
$tree->insert($tree->root, 60);
$tree->insert($tree->root, 80);

echo "Inorder Traversal of Binary Search Tree: ";
$tree->inorderTraversal($tree->root);
echo "\n";
?>

Output:

Inorder Traversal of Binary Search Tree: 20 30 40 50 60 70 80

Python Implementation of a Binary Search Tree

class Node:
    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None

def insert(root, key):
    if root is None:
        return Node(key)

    if key < root.data:
        root.left = insert(root.left, key)
    elif key > root.data:
        root.right = insert(root.right, key)

    return root

def inorderTraversal(root):
    if root:
        inorderTraversal(root.left)
        print(root.data, end=" ")
        inorderTraversal(root.right)

# Driver code
root = None
root = insert(root, 50)
insert(root, 30)
insert(root, 20)
insert(root, 40)
insert(root, 70)
insert(root, 60)
insert(root, 80)

print("Inorder Traversal of Binary Search Tree: ", end="")
inorderTraversal(root)
print()

Output:

Inorder Traversal of Binary Search Tree: 20 30 40 50 60 70 80

3. Heap Implementation

C++ Implementation of a Max-Heap

#include <iostream>
using namespace std;

void heapify(int arr[], int n, int i) {
    int largest = i; // Initialize largest as root
    int left = 2 * i + 1;
    int right = 2 * i + 2;

    if (left < n && arr[left] > arr[largest])
        largest = left;

    if (right < n && arr[right] > arr[largest])
        largest = right;

    if (largest != i) {
        swap(arr[i], arr[largest]);
        heapify(arr, n, largest);
    }
}

void buildHeap(int arr[], int n) {
    for (int i = n / 2 - 1; i >= 0; i--)
        heapify(arr, n, i);
}

void printHeap(int arr[], int n) {
    for (int i = 0; i < n; ++i)
        cout << arr[i] << " ";
    cout << endl;
}

int main() {
    int arr[] = {10, 20, 15, 30, 40};
    int n = sizeof(arr) / sizeof(arr[0]);

    buildHeap(arr, n);

    cout << "Max-Heap array: ";
    printHeap(arr, n);

    return 0;
}

Output:

Max-Heap array: 40 30 15 10 20

C Implementation of a Max-Heap

#include <stdio.h>

void heapify(int arr[], int n, int i) {
    int largest = i; // Initialize largest as root
    int left = 2 * i + 1;
    int right = 2 * i + 2;

    if (left < n && arr[left] > arr[largest])
        largest = left;

    if (right < n && arr[right] > arr[largest])
        largest = right;

    if (largest != i) {
        int temp = arr[i];
        arr[i] = arr[largest];
        arr[largest] = temp;

        heapify(arr, n, largest);
    }
}

void buildHeap(int arr[], int n) {
    for (int i = n / 2 - 1; i >= 0; i--)
        heapify(arr, n, i);
}

void printHeap(int arr[], int n) {
    for (int i = 0; i < n; ++i)
        printf("%d ", arr[i]);
    printf("\n");
}

int main() {
    int arr[] = {10, 20, 15, 30, 40};


 int n = sizeof(arr) / sizeof(arr[0]);

    buildHeap(arr, n);

    printf("Max-Heap array: ");
    printHeap(arr, n);

    return 0;
}

Output:

Max-Heap array: 40 30 15 10 20

C# Implementation of a Max-Heap

using System;

class MaxHeap {
    void Heapify(int[] arr, int n, int i) {
        int largest = i;
        int left = 2 * i + 1;
        int right = 2 * i + 2;

        if (left < n && arr[left] > arr[largest])
            largest = left;

        if (right < n && arr[right] > arr[largest])
            largest = right;

        if (largest != i) {
            int temp = arr[i];
            arr[i] = arr[largest];
            arr[largest] = temp;

            Heapify(arr, n, largest);
        }
    }

    void BuildHeap(int[] arr, int n) {
        for (int i = n / 2 - 1; i >= 0; i--)
            Heapify(arr, n, i);
    }

    void PrintHeap(int[] arr, int n) {
        for (int i = 0; i < n; i++)
            Console.Write(arr[i] + " ");
        Console.WriteLine();
    }

    public static void Main(String[] args) {
        MaxHeap maxHeap = new MaxHeap();
        int[] arr = {10, 20, 15, 30, 40};
        int n = arr.Length;

        maxHeap.BuildHeap(arr, n);

        Console.Write("Max-Heap array: ");
        maxHeap.PrintHeap(arr, n);
    }
}

Output:

Max-Heap array: 40 30 15 10 20

Java Implementation of a Max-Heap

class MaxHeap {
    void heapify(int[] arr, int n, int i) {
        int largest = i;
        int left = 2 * i + 1;
        int right = 2 * i + 2;

        if (left < n && arr[left] > arr[largest])
            largest = left;

        if (right < n && arr[right] > arr[largest])
            largest = right;

        if (largest != i) {
            int swap = arr[i];
            arr[i] = arr[largest];
            arr[largest] = swap;

            heapify(arr, n, largest);
        }
    }

    void buildHeap(int[] arr, int n) {
        for (int i = n / 2 - 1; i >= 0; i--)
            heapify(arr, n, i);
    }

    void printHeap(int[] arr, int n) {
        for (int i = 0; i < n; ++i)
            System.out.print(arr[i] + " ");
        System.out.println();
    }

    public static void main(String[] args) {
        MaxHeap maxHeap = new MaxHeap();
        int[] arr = {10, 20, 15, 30, 40};
        int n = arr.length;

        maxHeap.buildHeap(arr, n);

        System.out.print("Max-Heap array: ");
        maxHeap.printHeap(arr, n);
    }
}

Output:

Max-Heap array: 40 30 15 10 20

PHP Implementation of a Max-Heap

<?php
function heapify(&$arr, $n, $i) {
    $largest = $i;
    $left = 2 * $i + 1;
    $right = 2 * $i + 2;

    if ($left < $n && $arr[$left] > $arr[$largest])
        $largest = $left;

    if ($right < $n && $arr[$right] > $arr[$largest])
        $largest = $right;

    if ($largest != $i) {
        $temp = $arr[$i];
        $arr[$i] = $arr[$largest];
        $arr[$largest] = $temp;

        heapify($arr, $n, $largest);
    }
}

function buildHeap(&$arr, $n) {
    for ($i = $n / 2 - 1; $i >= 0; $i--)
        heapify($arr, $n, $i);
}

function printHeap($arr, $n) {
    for ($i = 0; $i < $n; ++$i)
        echo $arr[$i] . " ";
    echo "\n";
}

$arr = array(10, 20, 15, 30, 40);
$n = count($arr);

buildHeap($arr, $n);

echo "Max-Heap array: ";
printHeap($arr, $n);
?>

Output:

Max-Heap array: 40 30 15 10 20

Python Implementation of a Max-Heap

def heapify(arr, n, i):
    largest = i
    left = 2 * i + 1
    right = 2 * i + 2

    if left < n and arr[left] > arr[largest]:
        largest = left

    if right < n and arr[right] > arr[largest]:
        largest = right

    if largest != i:
        arr[i], arr[largest] = arr[largest], arr[i]
        heapify(arr, n, largest)

def buildHeap(arr):
    n = len(arr)
    for i in range(n // 2 - 1, -1, -1):
        heapify(arr, n, i)

def printHeap(arr):
    print(" ".join(str(x) for x in arr))

arr = [10, 20, 15, 30, 40]
buildHeap(arr)
print("Max-Heap array: ", end="")
printHeap(arr)

Output:

Max-Heap array: 40 30 15 10 20

4. Hashing Implementation (Hash Table)

C++ Implementation of a Simple Hash Table (Linear Probing)

#include <iostream>
using namespace std;

const int TABLE_SIZE = 10;

class HashTable {
    int* table;

public:
    HashTable() {
        table = new int[TABLE_SIZE];
        for (int i = 0; i < TABLE_SIZE; i++)
            table[i] = -1;  // -1 indicates an empty slot
    }

    int hashFunction(int key) {
        return key % TABLE_SIZE;
    }

    void insert(int key) {
        int hashIndex = hashFunction(key);
        while (table[hashIndex] != -1) {
            hashIndex = (hashIndex + 1) % TABLE_SIZE;
        }
        table[hashIndex] = key;
    }

    void display() {
        for (int i = 0; i < TABLE_SIZE; i++) {
            if (table[i] == -1)
                cout << i << ": Empty\n";
            else
                cout << i << ": " << table[i] << "\n";
        }
    }
};

int main() {
    HashTable hashTable;

    hashTable.insert(12);
    hashTable.insert(22);
    hashTable.insert(42);
    hashTable.insert(32);

    cout << "Hash Table:\n";
    hashTable.display();

    return 0;
}

Output:

Hash Table:
0: Empty
1: Empty
2: Empty
3: Empty
4: 12
5: 22
6: Empty
7: 32
8: 42
9: Empty

C Implementation of a Simple Hash Table (Linear Probing)

#include <stdio.h>

#define TABLE_SIZE 10

int table[TABLE_SIZE];

void initTable() {
    for (int i = 0; i < TABLE_SIZE; i++)
        table[i] = -1;  // -1 indicates an empty slot
}

int hashFunction(int key) {
    return key % TABLE_SIZE;
}

void insert(int key) {
    int hashIndex = hashFunction(key);
    while (table[hashIndex] != -1) {
        hashIndex = (hashIndex + 1) % TABLE_SIZE;
    }
    table[hashIndex] = key;
}

void display() {
    for (int i = 0; i < TABLE_SIZE; i++) {
        if (table[i] == -1)
            printf("%d: Empty\n", i);
        else
            printf("%d: %d\n", i, table[i]);
    }
}

int main() {
    initTable();

    insert(12);
    insert(22);
    insert(42);
    insert(32);

    printf("Hash Table:\n");
    display();

    return 0;
}

Output:

Hash Table:
0: Empty
1: Empty
2: Empty
3: Empty
4: 12
5: 22
6: Empty
7: 32
8: 42
9: Empty

Conclusion

Hierarchical data structures such as binary trees, binary search trees (BSTs), heaps, and hashing are cornerstones of efficient data management. Each structure has its own strengths and applications, making them essential tools for computer scientists and developers alike. Whether it’s managing a directory of files, maintaining a priority queue, or performing rapid search operations, understanding and applying these structures is critical for developing scalable and efficient software.

Frequently Asked Questions (FAQs) on Hierarchical Data Structures

What is a Binary Tree, and how is it different from other hierarchical data structures?

A binary tree is a hierarchical data structure in which each node has at most two children, commonly referred to as the left child and the right child. This structure is different from general tree structures in which a node can have more than two children. The key characteristic of a binary tree is its binary nature, which imposes specific rules on how data is organized and accessed.

While general trees like n-ary trees allow for any number of children per node, binary trees are more restricted, which often leads to more efficient algorithms for searching, inserting, and deleting data. Binary trees are used in various algorithms, such as tree traversal techniques and arithmetic expression evaluation.

What are the main types of binary trees?

There are several types of binary trees, each serving different purposes:

Full Binary Tree: A binary tree where every node has either 0 or 2 children. No nodes have only one child.
Complete Binary Tree: A binary tree that is entirely filled on all levels except possibly the last, where all nodes are as far left as possible.
Perfect Binary Tree: A binary tree in which all internal nodes have two children, and all leaves are at the same level. It is a special case of both a full and complete binary tree.
Balanced Binary Tree: A binary tree where the difference in heights between the left and right subtrees of any node is no more than one. AVL Trees and Red-Black Trees are examples of balanced binary trees.
Degenerate (or Skewed) Binary Tree: A binary tree where each node has only one child. This structure effectively behaves like a linked list.

Each type of binary tree has specific use cases depending on whether the focus is on search efficiency, memory utilization, or other factors.

What is the difference between a Binary Tree and a Binary Search Tree (BST)?

A binary tree is a general structure where each node can have at most two children. There are no restrictions on how the data is stored in the nodes. On the other hand, a binary search tree (BST) is a specific type of binary tree with the following property: for every node, all values in the left subtree are less than the node’s value, and all values in the right subtree are greater than the node’s value.

This property enables efficient searching, insertion, and deletion operations. The time complexity of these operations in a BST is O(h), where h is the height of the tree. In a balanced BST, this becomes O(log n), making BSTs a powerful tool for searching and sorting applications.

What are the common traversal methods in Binary Trees, and what are their use cases?

There are several ways to traverse a binary tree, each with different use cases:

Inorder Traversal (Left-Root-Right): In inorder traversal, the left subtree is visited first, followed by the root, and finally the right subtree. This traversal yields a sorted sequence of values for binary search trees (BSTs). It is commonly used in sorting algorithms and for operations that require ordered data.
Preorder Traversal (Root-Left-Right): In preorder traversal, the root is visited first, followed by the left and right subtrees. This method is often used to copy a tree or to generate prefix expressions in arithmetic operations.
Postorder Traversal (Left-Right-Root): In postorder traversal, the left subtree is visited first, then the right subtree, and finally the root. This traversal is commonly used for deleting a tree or for evaluating arithmetic expressions.
Level-Order Traversal (Breadth-First Search): Level-order traversal visits nodes level by level from top to bottom. This method is useful when we need to access nodes in the order of their depth or for algorithms like finding the shortest path in unweighted graphs.

What are the key operations in a Binary Search Tree (BST)?

In a binary search tree (BST), the following are the key operations:

Search: The search operation begins at the root and proceeds based on whether the value being searched for is smaller or larger than the current node. The time complexity is O(h), where h is the height of the tree.
Insertion: To insert a new node, we start at the root and navigate left or right depending on whether the new node’s value is smaller or larger than the current node. Once we find an appropriate leaf, we insert the new node. The time complexity is O(h).
Deletion: The deletion operation is more complex. There are three cases:

The node to be deleted is a leaf (it can be removed directly).
The node to be deleted has one child (the child is linked directly to the parent of the node).
The node to be deleted has two children (in this case, we replace the node with its inorder predecessor or inorder successor and remove the replaced node).

Traversal: We can traverse the BST using inorder, preorder, or postorder traversal methods, depending on the operation needed.

These operations enable BSTs to serve efficiently as data structures for implementing sets, maps, and dynamically ordered lists.

What is a Binary Heap, and how does it differ from a Binary Search Tree (BST)?

A binary heap is a complete binary tree that satisfies the heap property. There are two types of heaps:

Min-Heap: The value of each node is less than or equal to the values of its children.
Max-Heap: The value of each node is greater than or equal to the values of its children.

In contrast, a binary search tree (BST) ensures that, for each node, the left subtree contains values less than the node, and the right subtree contains values greater than the node. This makes BSTs efficient for search operations, while heaps are designed for efficient priority queue operations, such as retrieving the minimum (in a min-heap) or maximum (in a max-heap) element.

The main operations in heaps, such as extract-min or insert, are performed in O(log n) time, while BSTs allow for efficient searching, insertion, and deletion.

What is the role of a Binary Heap in Priority Queues?

A priority queue is an abstract data type in which elements are processed based on their priority rather than their insertion order. A binary heap is commonly used to implement priority queues because it provides efficient access to the minimum (in a min-heap) or maximum (in a max-heap) element in constant time O(1), and allows for insertion and deletion in O(log n) time.

In a min-heap, for instance, the extract-min operation retrieves the smallest element (the root) and restructures the heap to maintain the heap property. This makes heaps particularly useful in algorithms like Dijkstra’s shortest path algorithm and Prim’s minimum spanning tree algorithm.

What is Hashing, and how does it achieve constant time complexity?

Hashing is a technique used to map data to a fixed-size table (called a hash table) using a hash function. The primary goal of hashing is to achieve O(1) time complexity for search, insert, and delete operations, under ideal conditions.

A hash function takes an input (a key) and produces an output (the hash code or index) that determines where the key-value pair should be stored in the hash table. However, collisions can occur when two different keys generate the same hash code. Collision resolution techniques, such as chaining or open addressing, are used to handle these cases.

Hashing is widely used in databases, compilers, and caching systems for quick lookups and data retrieval.

What is a Hash Function, and what are its desired properties?

A hash function is a function that converts an input (or “key”) into a fixed-size string of bytes, typically used as an index to store data in a hash table. The main purpose of a hash function is to distribute keys evenly across the hash table to minimize collisions.

The desired properties of a good hash function are:

Deterministic: The same input should always yield the same hash value.
Efficient: The hash function should be fast to compute, even for large inputs.
Uniform Distribution: It should distribute keys uniformly across the hash table to avoid clustering and minimize collisions.
Low Collision Rate: Although collisions (when two different inputs generate the same hash value) are inevitable, a good hash function minimizes them.
Avalanche Effect: A small change in the input should result in a significant change in the hash value.

Common hash functions include MD5, SHA-256, and MurmurHash, each designed with different strengths and trade-offs.

What are Collisions in Hashing, and how are they handled?

A collision in hashing occurs when two different keys generate the same hash value and thus map to the same location in the hash table. Since each location in a hash table can ideally store only one item, collision handling mechanisms are required. The two most common methods are:

Chaining: Each index in the hash table points to a linked list (or another data structure like a balanced binary tree) that stores all key-value pairs that hash to that index. When a collision occurs, the new key-value pair is appended to the list.
Open Addressing: Instead of using a linked list to handle collisions, open addressing searches for the next available slot in the hash table. There are different strategies for open addressing:
Linear Probing: If a collision occurs, check the next slot (index + 1), and so on.
Quadratic Probing: Use a quadratic formula to determine the next slot to check (index + i²).
Double Hashing: Use a second hash function to determine the next slot if a collision occurs.

Collisions are inevitable in hashing, but these methods ensure that the hash table remains operational even when collisions happen frequently.

How does Hashing improve the efficiency of Search, Insert, and Delete operations?

Hashing improves the efficiency of search, insert, and delete operations by reducing the need to traverse through large data structures like arrays or linked lists. In an ideal scenario, the time complexity of these operations in a hash table is O(1) because the hash function directly computes the index where the data should be stored or retrieved.

Search: The key is passed through the hash function to generate an index, and the value associated with that index can be retrieved instantly.
Insert: The key-value pair is stored at the index computed by the hash function.
Delete: The key is passed through the hash function, and the associated value can be removed from the computed index.

However, in the case of collisions, the time complexity can degrade to O(n), but efficient collision resolution techniques such as chaining or open addressing help maintain average-case O(1) time complexity.

What are the differences between Chaining and Open Addressing in Hash Tables?

Chaining and open addressing are two primary methods for handling collisions in hash tables:

Chaining: In this method, each index in the hash table points to a linked list (or other data structure) that holds all key-value pairs that hash to the same index. When a collision occurs, the new element is simply added to the list.
Advantages:
- Easy to implement.
- A hash table can store more elements than the number of available slots.
Disadvantages:
- May require additional memory for the linked lists.
- Performance can degrade if many collisions occur, leading to long lists.
Open Addressing: In open addressing, all elements are stored directly in the hash table, and if a collision occurs, the algorithm searches for the next available slot. There are several strategies for open addressing, such as:
Linear Probing: Check subsequent slots until an empty one is found.
Quadratic Probing: Check slots according to a quadratic function.
Double Hashing: Use a second hash function to determine the next slot.
Advantages:
- More space-efficient since no additional memory (e.g., for linked lists) is required.
- All elements are stored in the hash table itself, simplifying data access.
Disadvantages:
- Performance degrades when the table becomes too full, leading to clustering.
- Deletion is more complex, as it may affect future searches.

What is the significance of Load Factor in Hashing, and how does it affect performance?

The load factor of a hash table is the ratio of the number of elements stored to the total size of the hash table. It is calculated as:

$$
\text{Load Factor} = \frac{\text{Number of Elements}}{\text{Table Size}}
$$

The load factor directly affects the performance of the hash table:

Low Load Factor: If the load factor is too low (i.e., the hash table has many empty slots), the hash table will consume more memory than necessary. However, the search, insert, and delete operations will be more efficient since there will be fewer collisions.
High Load Factor: A high load factor means that the table is becoming full, increasing the likelihood of collisions. As the load factor increases, the time complexity of search, insert, and delete operations may degrade from O(1) to O(n) in the worst case.

To maintain optimal performance, hash tables are typically resized when the load factor exceeds a certain threshold (commonly around 0.7). Resizing involves creating a new hash table with a larger size and rehashing all elements into the new table, which can be an expensive operation but is necessary to keep the load factor low.

What is the difference between a Min-Heap and a Max-Heap?

A min-heap and a max-heap are both types of binary heaps, but they differ in the way they order the elements:

Min-Heap: In a min-heap, the value of each node is less than or equal to the values of its children. The smallest element is stored at the root. Min-heaps are typically used in applications like Dijkstra’s algorithm for finding the shortest path.
Max-Heap: In a max-heap, the value of each node is greater than or equal to the values of its children. The largest element is stored at the root. Max-heaps are often used in implementing priority queues when the maximum priority element needs to be accessed quickly.

Both heaps are complete binary trees, and their primary operations, such as insert, delete, and extract-min or extract-max, can be performed in O(log n) time.

What are some real-world applications of Binary Trees and Hashing?

Binary trees and hashing are foundational concepts with a wide range of real-world applications:

Binary Trees:
Database Indexing: Balanced binary search trees (BSTs), such as AVL trees and red-black trees, are used to implement database indices that allow for fast search, insert, and delete operations.
Expression Parsing: In compilers, binary trees are used to parse arithmetic expressions and generate intermediate code representations for evaluation.
File Systems: Binary trees help manage hierarchical file systems, where directories are represented as nodes and subdirectories or files are stored in child nodes.
Hashing:
Password Verification: Hashing is extensively used in password storage systems. Passwords are hashed before being stored in a database, and the stored hash is compared during user authentication.
Caching: Web browsers and content delivery networks (CDNs) use hashing to cache frequently accessed resources, such as images or web pages, by hashing URLs.
Load Balancing: Hashing algorithms help distribute tasks or requests across multiple servers in distributed systems, ensuring that no server is overloaded.
Blockchain and Cryptography: Cryptographic hash functions like SHA-256 are used to secure blockchain transactions and create unique digital signatures in cryptographic systems.

Hierarchical Data Structures: Binary Trees, Binary Search Trees, Heaps, & Hashing

Table of Contents

Binary Tree: A Foundational Hierarchical Data Structure

Binary Tree Representation

Binary Tree Traversals

Properties of a Binary Tree

Basic Operations on Binary Trees

Auxiliary Operations

Applications of Binary Trees

Binary Search Tree (BST): Fast Search in Hierarchical Data Structure

Binary Search Tree Declaration

Primary Operations in BST

Auxiliary Operations

Balanced vs. Unbalanced BSTs

Applications of Binary Search Trees

Binary Heap: A Complete Binary Tree

Properties of a Binary Heap

Operations on Binary Heaps

Applications of Binary Heaps

Hashing: The Fastest Search Technique

Hash Function

Hash Table

Collision Handling Techniques

Time Complexity of Hashing

Applications of Hashing

Detailed Examples of Binary Trees, Binary Search Trees (BSTs), Heaps, and Hashing Implementations

1. Binary Tree Implementation

C++ Implementation of a Binary Tree

Output:

C Implementation of a Binary Tree

Output:

C# Implementation of a Binary Tree

Output:

Java Implementation of a Binary Tree

Output:

PHP Implementation of a Binary Tree

Output:

Python Implementation of a Binary Tree

Output:

2. Binary Search Tree (BST) Implementation

C++ Implementation of a Binary Search Tree

Output:

C Implementation of a Binary Search Tree

Output:

C# Implementation of a Binary Search Tree

Output:

Java Implementation of a Binary Search Tree

Output:

PHP Implementation of a Binary Search Tree

Output:

Python Implementation of a Binary Search Tree

Output:

3. Heap Implementation

C++ Implementation of a Max-Heap

Output:

C Implementation of a Max-Heap

Output:

C# Implementation of a Max-Heap

Output:

Java Implementation of a Max-Heap

Output:

PHP Implementation of a Max-Heap

Output:

Python Implementation of a Max-Heap

Output:

4. Hashing Implementation (Hash Table)

C++ Implementation of a Simple Hash Table (Linear Probing)

Output:

C Implementation of a Simple Hash Table (Linear Probing)

Output:

Conclusion

Related Articles

Read More Articles

Frequently Asked Questions (FAQs) on Hierarchical Data Structures

What is a Binary Tree, and how is it different from other hierarchical data structures?

What are the main types of binary trees?

What is the difference between a Binary Tree and a Binary Search Tree (BST)?

What are the common traversal methods in Binary Trees, and what are their use cases?

What are the key operations in a Binary Search Tree (BST)?

What is a Binary Heap, and how does it differ from a Binary Search Tree (BST)?