Tree ( DSA - 8 )

Tree is a hierarchical data structure that consists of nodes connected by edges. It is a non-linear structure, which means that unlike arrays, linked lists, stacks, or queues, elements are not arranged in a sequential manner.

Basic Concepts:

Root:
The topmost node in the tree. There is exactly one root node in a tree.
Nodes:
Basic units of a tree containing data and references to other nodes.
Edges:
Links between nodes, showing the relationship from parent to child.
Parent:
A node that has one or more child nodes.
Child:
A node that has a parent node.
Leaf/Terminal node:
A node that does not have any children.
Subtree:
Any node of a tree, along with its descendants, forms a subtree.
Height:'
The longest path from the root to any leaf.
Depth:
The number of edges from the root to the node.
Level:
The level of a node is determined by the distance from the root (root being level 0).

Types of Binary trees and their formulas:

1)Full Binary Tree:
Every node has either 0 or 2 children.

        1
       / \
      2   3
     / \ / \
    4  5 6  7

Number of Nodes: 2h+1 nodes(where h is the height).
Number of Leaf nodes: (n+1)/2​
Internal Nodes: (n-1)/2

2)Complete Binary Tree
All levels are fully filled except possibly the last, which is filled from left to right.

        1
       / \
      2   3
     / \  /
    4  5 6

Number of Nodes: (2^h - 2^(h+1)-1)
Height of the Tree: h= ⌊log(n)⌋
Number of Leaf Nodes: ⌈n/2⌉
Internal Nodes: ⌊n/2⌋

3)Perfect Binary Tree
All internal nodes have two children and all leaves are at the same level. It is always a complete, full and balanced binary tree.

        1
       / \
      2   3
     / \ / \
    4  5 6  7

Number of Nodes: 2^(h+1)-1
Height of the Tree: h= log(n+1)-1
Number of Leaf Nodes: 2^h
Internal Nodes: 2^h-1

4)Balanced Binary Tree
The height difference between left and right subtrees for any node is at most 1.

        1
       / \
      2   3
     / \
    4   5

Types of Trees:

AVL Tree

An AVL Tree is a type of self-balancing binary search tree (BST) named after its inventors, G.M. Adelson-Velsky and E.M. Landis, who introduced it in the early 1960s. It maintains its balance through a specific property which ensures that the heights of the two child subtrees of any node differ by no more than one.

Balance Factor=Height of Left Subtree−Height of Right Subtree
(The balance factor must be -1, 0, or 1 for all nodes to maintain the AVL property)

The height of an AVL tree with n nodes is O(logn). This ensures that operations like insertion, deletion, and search all have a time complexity of O(logn), making AVL trees efficient for dynamic data.

Applications:
Database indexing
In-memory data structures
Implementation of associative arrays and sets

Binary Tree

Each node has at most two children, known as the left child and the right child.

Minimum nodes(N):
No of nodes = N

Maximum nodes(N):
2^h+1 - 1 = N

Maximum Height:
n−1

Minimum Height:
⌊log₂(n+1)⌋

Heap

It is a special type of binary tree that satisfies the heap property. Heaps are commonly used to implement priority queues, which are abstract data structures where elements are retrieved according to their priority.

The left child is at index (2*i + 1)
The right child is at index (2*i + 2)
The parent is at index ((i - 1) / 2)
The index of last parent node ((n-1-1)/2)

Min Heap
In a min heap, the key (value) of each parent node is less than or equal to the keys of its children. The minimum element is always at the root (the top of the heap).

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

int main() {
    priority_queue<int, std::vector<int>, std::greater<int>> minHeap;

    minHeap.push(3);
    minHeap.push(2);
    minHeap.push(15);
    minHeap.push(5);
    minHeap.push(4);
    minHeap.push(45);

    cout << "Min Heap: ";
    while (!minHeap.empty()) {
        cout << minHeap.top() << " ";
        minHeap.pop();
    }

    return 0;
}

Max Heap
In a max heap, the key of each parent node is greater than or equal to the keys of its children. The maximum element is always at the root.

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

int main() {
    priority_queue<int> maxHeap;

    maxHeap.push(3);
    maxHeap.push(2);
    maxHeap.push(15);
    maxHeap.push(5);
    maxHeap.push(4);
    maxHeap.push(45);

    cout << "Max Heap: ";
    while (!maxHeap.empty()) {
        cout << maxHeap.top() << " ";
        maxHeap.pop();
    }

    return 0;
}

Is Max Heap:

    bool isMaxHeap(int arr[], int n)
    {
        for(int i=0;i<=(n-2)/2;i++){

            if(2*i+1 < n && arr[i]<arr[2*i+1]){
                return false;
            }
            if(2*i+2 < n && arr[i]<arr[2*i+2]){
                return false;
            }

        }
        return true;

    }

Kth Largest Element in an Array

    int findKthLargest(vector<int>& nums, int k) {
        priority_queue<int> max;

        for(auto each: nums){
            max.push(each);
        }
        int num;
        while(k--){
            num=max.top();
            max.pop();
        }
        return num;
    }

Kth Smallest Element in an array

    int kthSmallest(int arr[], int l, int r, int k) {
        priority_queue<int> maxHeap;

        for (int i = l; i <= r; ++i) {
            maxHeap.push(arr[i]);

            if (maxHeap.size() > k) {
                maxHeap.pop();
            }
        }

        return maxHeap.top();
    }

Binary Search Tree (BST)

A binary tree where the left child contains only nodes with values less than the parent node, and the right child contains only nodes with values greater than the parent node.

Binary Tree Algorithms

1) Insertion in Binary Search

TreeNode* insertNode(TreeNode* root, int value) {
    if (root == nullptr) return new TreeNode(value);
    if (value < root->val) root->left = insertNode(root->left, value);
    else root->right = insertNode(root->right, value);
    return root;
}

2) Searching in Binary Tree:

bool searchNode(TreeNode* root, int value) {
    if (root == nullptr) return false;
    if (root->val == value) return true;
    if (value < root->val) return searchNode(root->left, value);
    return searchNode(root->right, value);
}

3) Deletion from Binary Tree:

TreeNode* findMin(TreeNode* root) {
    while (root->left != nullptr) root = root->left;
    return root;
}

TreeNode* deleteNode(TreeNode* root, int value) {
    if (root == nullptr) return root;
    if (value < root->val) root->left = deleteNode(root->left, value);
    else if (value > root->val) root->right = deleteNode(root->right, value);
    else {
        if (root->left == nullptr) {
            TreeNode* temp = root->right;
            delete root;
            return temp;
        } else if (root->right == nullptr) {
            TreeNode* temp = root->left;
            delete root;
            return temp;
        }
        TreeNode* temp = findMin(root->right);
        root->val = temp->val;
        root->right = deleteNode(root->right, temp->val);
    }
    return root;
}

4) Finding the Height of Binary Tree

int height(TreeNode* root) {
    if (root == nullptr) return 0;
    int leftHeight = height(root->left);
    int rightHeight = height(root->right);
    return max(leftHeight, rightHeight) + 1;
}

5) Find ceil of a value

int findCeil(Node* root, int input) {

    int ceilValue = -1; 

    while (root != NULL) {
        if (root->data == input) {
            return root->data; 
        } else if (root->data < input) {
            root = root->right;
        } else {
            ceilValue = root->data
            root = root->left;
        }
    }

    return ceilValue;
}

6) Minimum value in BST
(Note: If Maximum value, use right side nodes)

int minValue(Node* root) {

    Node* temp = root;

    while (temp->left != NULL) {
        temp = temp->left;
    }

    return temp->data;
}

7) Is this BST?

bool isBSTTraversal(vector<int>& arr) {

    for (int i = 0; i < arr.size() - 1; i++) {
        if (arr[i+1] <= arr[i]) {
            return false; 
        }
    }
    return true;
}

8) Delete the middle node

class Solution {
    public ListNode deleteMiddle(ListNode head) {
        if (head == null || head.next == null) return null;
        ListNode slow = head;
        ListNode fast = head;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        fast = head;
        while (true) {
            if (fast.next == slow) {
                fast.next = fast.next.next;
                break;
            }
            fast = fast.next;
        }
        return head;
    }
}

Tree Traversal:

Note:
Preorder - 1
Inorder - 2 times
Postorder - 3

1) In-order (left, root, right)

void inorderTraversal (Node node) {
if (node != null) {
inorderTraversal (node.left);
System.out.println(node.key);
inorderTraversal (node.right);
}
}

2) Pre-order (root, left, right)

void preorder Traversal (Node node) {
if (node != null) {
System.out.print(node.key + ");
preorder Traversal (node.left);
preorder Traversal (node.right);
}

3) Post-order (left, right, root)

void postorderTraversal (Node node) {
if (node != null) {
postorder Traversal (node.left); 
postorder Traversal (node.right); 
System.out.print(node.key + ");
}
}

Stay Connected!
If you enjoyed this post, don’t forget to follow me on social media for more updates and insights:

Twitter: madhavganesan
Instagram: madhavganesan
LinkedIn: madhavganesan