DSA in Java Trees

Trees

A Tree is a non-linear hierarchical data structure consisting of nodes connected by edges.
It is widely used to represent data with a hierarchical relationship, such as organization charts, file systems, and expression parsers.

Basic Terminologies:

• Node:
  The basic unit of a tree that contains data.

• Root:
  The topmost node in a tree.
  The starting point of the tree structure.

• Edge:
  The connection between two nodes.

• Parent:
  The node that has one or more child nodes.

• Child:
  The node that descends from another node.

• Leaf (External Node):
  A node that has no children.

• Internal Node:
  A node that has at least one child.

• Subtree:
  A tree formed from a node and its descendants.

• Level:
  The depth or distance from the root node. The root is at level 0.

• Height of Tree:
    The maximum level of any node in the tree.

• Depth of Node:
    The distance from the root to the node.

Types of Trees:

General Tree:
A tree in which each node can have any number of children.

Binary Tree:
A tree in which each node has at most two children (left and right).

Binary Search Tree (BST):
A binary tree where the left child contains smaller values and the right child contains greater values.

Complete Binary Tree:
A binary tree in which all levels are completely filled except possibly the last, which is filled from left to right.

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

Balanced Binary Tree:
A tree where the difference of heights between left and right subtrees is at most 1.

AVL Tree, B-Tree, Heap Tree, Red-Black Tree:
Special forms of trees used in searching, sorting, and memory management.

Tree Traversals:

• Inorder (Left, Root, Right):
  Used in Binary Search Trees for sorted output.

• Preorder (Root, Left, Right):
  Used to create a copy of the tree.

• Postorder (Left, Right, Root):
  Used to delete/free the tree nodes.

• Level Order (Breadth-First):
  Visit nodes level by level from top to bottom.

Applications of Trees:

Hierarchical Data Representation: File systems, XML, HTML DOM.
Database Indexing: B-Trees, B+ Trees.
Searching Algorithms: Binary Search Trees, Heaps.
Expression Parsing: Expression Trees for arithmetic operations.
Network Routing Algorithms.

Advantages of Trees:

Reflects Real-World Hierarchies.
Efficient Searching, Insertion, Deletion.
Suitable for representing sorted data.

Limitations of Trees:

Complexity in Implementation.
Requires more memory due to pointers.
Balancing issues may arise in some trees (e.g., unbalanced BST).

Tree Representation (Diagram Example):

       [A]   ← Root

       /   \

     [B]   [C]

     / \     \

   [D] [E]   [F]  ← Leaves

Binary Trees (Insertion, Deletion, Recursive/Iterative Traversals)

Definition of Binary Tree:

A Binary Tree is a special form of a hierarchical data structure in which each node can have at most two children, referred to as the left child and the right child.

Basic Operations on Binary Trees:

Insertion in Binary Tree:

Insertion can be done either to:

• Maintain structure only (complete binary tree) — insert at the first available position.

• Maintain sorted order (Binary Search Tree) — insert left or right depending on the key value.

Algorithm for Insertion in Binary Search Tree (BST):

Step 1: If the tree is empty, create a new node as root.

Step 2: If the value to insert is less than the root, recursively insert in the left subtree.

Step 3: If the value is greater, recursively insert in the right subtree.

Recursive Insertion Example (C Code):

struct Node {

    int data;

    struct Node *left, *right;

};

struct Node* insert(struct Node* root, int key) {

    if(root == NULL) {

        struct Node* temp = (struct Node*)malloc(sizeof(struct Node));

        temp->data = key;

        temp->left = temp->right = NULL;

        return temp;

    }

    if(key < root->data)

        root->left = insert(root->left, key);

    else if(key > root->data)

        root->right = insert(root->right, key);

    return root;

}

Deletion in Binary Tree:

Deletion in Binary Search Tree has 3 cases:

• Node to be deleted is a Leaf Node:
  Simply remove the node.

• Node has One Child:
  Replace the node with its child.

• Node has Two Children:
  Find inorder successor/predecessor, replace node’s data, and delete the successor/predecessor node.

Recursive Deletion Example (C Code):

struct Node* deleteNode(struct Node* root, int key) {

    if(root == NULL) return root;

    if(key < root->data)

        root->left = deleteNode(root->left, key);

    else if(key > root->data)

        root->right = deleteNode(root->right, key);

    else {

        if(root->left == NULL) {

            struct Node* temp = root->right;

            free(root);

            return temp;

        }

        else if(root->right == NULL) {

            struct Node* temp = root->left;

            free(root);

            return temp;

        }

        // Node with two children

        struct Node* temp = minValueNode(root->right);

        root->data = temp->data;

        root->right = deleteNode(root->right, temp->data);

    }

    return root;

}

struct Node* minValueNode(struct Node* node) {

    struct Node* current = node;

    while(current && current->left != NULL)

        current = current->left;

    return current;

}

Tree Traversals:

Recursive Traversals:

Inorder (Left, Root, Right):
Yields sorted order in BST.

void inorder(struct Node* root) {

    if(root != NULL) {

        inorder(root->left);

        printf(“%d “, root->data);

        inorder(root->right);

    }

}

Preorder (Root, Left, Right):
Useful for creating tree copies.

void preorder(struct Node* root) {

    if(root != NULL) {

        printf(“%d “, root->data);

        preorder(root->left);

        preorder(root->right);

    }

}

Postorder (Left, Right, Root):
Used to delete/free nodes.

void postorder(struct Node* root) {

    if(root != NULL) {

        postorder(root->left);

        postorder(root->right);

        printf(“%d “, root->data);

    }

}

Iterative Traversals:

Iterative methods use a stack (for DFS) or queue (for BFS).

Inorder Traversal (Iterative)

void inorderIterative(struct Node* root) {

    struct Node* stack[100];

    int top = -1;

    while(root != NULL || top != -1) {

        while(root != NULL) {

            stack[++top] = root;

            root = root->left;

        }

        root = stack[top–];

        printf(“%d “, root->data);

        root = root->right;

    }

}

Level Order (BFS using Queue):

void levelOrder(struct Node* root) {

    if(root == NULL) return;

    struct Node* queue[100];

    int front = 0, rear = 0;

    queue[rear++] = root;

    while(front < rear) {

        struct Node* temp = queue[front++];

        printf(“%d “, temp->data);

        if(temp->left != NULL) queue[rear++] = temp->left;

        if(temp->right != NULL) queue[rear++] = temp->right;

    }

}

Applications of Binary Trees:

Binary Search Trees for efficient searching and sorting.
Expression trees in compilers.
Decision trees in AI.
Heap Trees for priority queues.
File system directories.

Advantages:

Hierarchical data storage.
Faster searching, insertion, and deletion in BST (O(log n) for balanced trees).

Limitations:

Unbalanced BST may degrade performance to O(n).
Requires extra memory for pointers.

Threaded Binary Trees

A Threaded Binary Tree is a modified version of a binary tree in which the NULL pointers are replaced by special pointers (called threads). These threads are used to make the inorder traversal of the binary tree faster and more memory-efficient by eliminating the need for a stack or recursion.

A threaded binary tree helps in traversing the tree without using a stack or recursion by connecting nodes through these threads.

Need for Threaded Binary Trees:

In a normal binary tree, many pointers (especially in leaf nodes) are NULL.
These unused NULL pointers can be replaced by threads pointing to the inorder predecessor or successor, reducing the need for extra memory (like stacks).

Types of Threaded Binary Trees:

Single Threaded Binary Tree:

A binary tree where:

• Left NULL pointers are used to store the inorder predecessor
  or

• Right NULL pointers are used to store the inorder successor.

Double Threaded Binary Tree:

A binary tree where:

• Both left and right NULL pointers are replaced by threads pointing to inorder predecessor and inorder successor respectively.

Structure of a Node in Threaded Binary Tree (C Example):

struct Node {

    int data;

    struct Node *left, *right;

    int lthread, rthread; // Flags to indicate if pointers are threads

};

lthread = 1: Left pointer is a thread (points to predecessor).
rthread = 1: Right pointer is a thread (points to successor).

Inorder Traversal in Threaded Binary Tree:

Can be done without recursion or stack:

void inorder(struct Node* root) {

    struct Node* curr = leftmost(root);

    while(curr != NULL) {

        printf(“%d “, curr->data);

        if(curr->rthread)

            curr = curr->right;

        else

            curr = leftmost(curr->right);

    }

}

struct Node* leftmost(struct Node* node) {

    while(node != NULL && node->lthread == 0)

        node = node->left;

    return node;

}

Advantages of Threaded Binary Tree:

Inorder traversal without recursion or stack.
Saves memory as no explicit stack is required.
Makes traversal faster and efficient.
Useful in applications like symbol tables, expression trees, etc..

Limitations of Threaded Binary Tree:

Insertion and Deletion operations are more complex compared to standard binary trees.
Rarely used in modern high-level implementations because of availability of automatic stack management by modern compilers.

Applications of Threaded Binary Trees:

Efficient tree traversal (inorder, preorder) without recursion.
Suitable for memory-constrained systems.
Used in compiler design, expression parsing, and database indexing.

Diagram (Conceptual View of Threads):

        [10]

        /    \

     [5]    [15]

       \    /

       [7][12]

(Where NULL pointers are replaced with threads to predecessor/successor)

Height-Balanced Trees

A Height-Balanced Tree is a type of binary tree in which the height difference between the left and right subtrees of every node is either 0 or 1.

Such trees are designed to keep operations like searching, insertion, and deletion efficient (in O(log n) time) by ensuring the tree remains approximately balanced.

Balance Factor:

For every node in a height-balanced tree:

Balance Factor=Height of Left Subtree−Height of Right Subtree\text{Balance Factor} = \text{Height of Left Subtree} – \text{Height of Right Subtree}Balance Factor=Height of Left Subtree−Height of Right Subtree

The tree is said to be height-balanced if the balance factor of each node is -1, 0, or +1.

Types of Height-Balanced Trees:

AVL Tree (Adelson-Velsky and Landis Tree):

The first self-balancing binary search tree.
After every insertion or deletion, the tree checks balance factors and performs rotations to maintain balance.

Red-Black Tree:

A height-balanced binary search tree with extra bit (red or black) to ensure balance rules.
Commonly used in STL (C++) and Java TreeMap/TreeSet.

B-Trees and B+ Trees:

Multi-way search trees used in databases and file systems to store data that does not fit in RAM.
Keeps tree height logarithmic relative to the number of elements.

Properties of Height-Balanced Trees:

Balanced Height: Ensures height is logarithmic to number of nodes (O(log n)).
Efficient Operations: Search, insert, delete — all in O(log n) time complexity.
Prevents Skewness: Avoids degeneration into a linear structure like a linked list.

Rotations in AVL Trees (For Maintaining Balance):

Left Rotation
Right Rotation
Left-Right Rotation
Right-Left Rotation

These rotations are applied after insertions or deletions to restore balance.

Example:

A balanced AVL Tree:

markdown

     30

     /  \

   20    40

  /  \

10   25

Each node’s balance factor: 0, -1, 1 — so the tree is balanced.

Advantages of Height-Balanced Trees:

Efficient Searching: O(log n) time for all major operations.
Prevents performance degradation as seen in unbalanced BSTs (O(n)).
Applicable to large datasets such as databases and memory management systems.

Limitations of Height-Balanced Trees:

Complex implementation (due to rotations, balancing).
Slightly more memory overhead (to store balance information or colors).

Applications of Height-Balanced Trees:

Databases indexing (B-Trees, B+ Trees).
Memory management (AVL trees in real-time systems).
File systems (NTFS, Ext4).
Map/Set implementations in programming libraries (Red-Black Trees in C++ STL).

AVL Tree Operations

Definition of AVL Tree:

An AVL Tree (named after Adelson-Velsky and Landis) is a self-balancing Binary Search Tree (BST) where the difference between heights of left and right subtrees (Balance Factor) for any node is not more than 1.

Balance Factor (BF) = Height of Left Subtree – Height of Right Subtree
BF should be -1, 0, or +1 for all nodes.

✅ Important AVL Tree Operations:

Insertion:

Insert the new node as in a normal BST.
After insertion, update the balance factor of nodes.
If a node becomes unbalanced, perform rotation(s) to balance the tree.

Types of Rotations in AVL Tree (For Balancing):

• Left-Left (LL) Rotation:
  Used when insertion is in the left subtree of the left child.

• Right-Right (RR) Rotation:
  Used when insertion is in the right subtree of the right child.

• Left-Right (LR) Rotation:
  Used when insertion is in the right subtree of the left child.

• Right-Left (RL) Rotation:
  Used when insertion is in the left subtree of the right child.

Example: LL Rotation

markdown

    30

    /

  20

  /

10

Here, LL imbalance occurs at node 30 — apply Right Rotation.

After rotation:

  20

  /  \

10   30

Deletion:

Delete the node as in BST deletion.
After deletion, update the balance factors and re-balance the tree by applying suitable rotations.

Cases to Consider After Deletion:

Left-Left (LL) Imbalance – Apply Right Rotation.
Right-Right (RR) Imbalance – Apply Left Rotation.
Left-Right (LR) Imbalance – Apply Left-Right Rotation.
Right-Left (RL) Imbalance – Apply Right-Left Rotation.

Searching:

Searching is similar to a normal BST but faster because the tree remains balanced, ensuring O(log n) time complexity.

Complexity of AVL Tree Operations:

Advantages of AVL Tree:

Self-balancing: Always maintains O(log n) height.
Faster searches, insertions, deletions than unbalanced BST.
Guarantees worst-case time complexity of O(log n).

Limitations:

Rotations introduce overhead during insertions and deletions.
More complex to implement compared to simple BSTs.

Applications of AVL Tree:

Databases and indexing systems.
Memory management in real-time systems.
Suitable when frequent insertions and deletions occur.