CODEBHAVYA • DATA STRUCTURES

🌳 Trees

Understand hierarchical data, learn essential Tree terminology, study Binary Tree structure, build a small Binary Tree, and trace the exact C program step by step.

TREE INTRODUCTION

📖 What is a Tree?

A tree is a non-linear hierarchical data structure made of nodes connected by edges. Unlike an array, linked list, stack, or queue, Tree data is organized in levels.

💡 Hierarchical Structure

A Tree begins with one top node called the root. A node can connect downward to child nodes, and those children can have their own children.

🧠 Real-Life Examples

Folder structures, organization charts, HTML DOM, family hierarchies, decision trees, expression trees, and database indexes can all be modeled using Trees.

10
ROOT
20
30
40
50
60
70
LEAF
LEAF
TERMINOLOGY

🧩 Important Tree Terms

Root The topmost node. A non-empty Tree has exactly one root.
Parent A node that has one or more child nodes.
Child A node directly connected below another node.
Siblings Nodes that share the same parent.
Leaf Node A node with no children.
Internal Node A node with at least one child.
Edge A connection between a parent and a child.
Depth Number of edges from the root to a node.
Height Number of edges on the longest downward path from a node to a leaf.
Subtree A node together with all of its descendants.
Ancestor Any node on the path from the root to a given node, excluding the node itself.
Descendant Any node reachable by moving downward from a given node.

📌 Convention Used on CodeBhavya

The root is at depth 0. Tree height is measured in edges, so a single-node Tree has height 0.

BINARY TREE

🌿 Binary Tree Basics

A Binary Tree is a Tree in which every node has at most two children. These are called the left child and right child.

Maximum Children Each node can have 0, 1, or 2 children.
Left Child Stored using the node's left pointer.
Right Child Stored using the node's right pointer.

🧠 In Our Example

Node 10 is the root. Nodes 20 and 30 are its children. Nodes 40 and 50 are children of 20. Nodes 60 and 70 are children of 30.

NODE STRUCTURE

🧱 Binary Tree Node in C

A Binary Tree node normally stores one data field and two pointer fields.

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

💡 Meaning of NULL

If left == NULL, the node has no left child. If right == NULL, the node has no right child. A leaf node has both pointers equal to NULL.

CONSTRUCTION

⚙️ Building a Small Binary Tree

For this first Tree lesson, we create nodes individually and connect them using left and right pointers. 

CREATE_NODE(value)

1. Allocate memory for a new node
2. newNode->data = value
3. newNode->left = NULL
4. newNode->right = NULL
5. Return newNode
BUILD EXAMPLE

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)

🔗 Pointer View

The values do not have to be stored next to each other in memory. The Tree structure is created by the left and right pointer connections.

VISUALIZER

🎬 Build a Binary Tree Visually

INTERACTIVE ALGORITHM VISUALIZATION
CodeBhavya CodeBhavya
🎬 Premium Binary Tree Builder Enter level-order values and watch each node attach to its parent. Use null or - for an empty position.
Root —
Current Node —
Parent —
Nodes Built 0
Press Next to begin building the Binary Tree.
C PROGRAM

💻 Create a Binary Tree in C

Visible Learning Program

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

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

struct Node *createNode(int value)
{
    struct Node *newNode =
        (struct Node *)malloc(sizeof(struct Node));

    newNode->data = value;
    newNode->left = NULL;
    newNode->right = NULL;

    return newNode;
}

int main()
{
    struct Node *root;

    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("Root: %d\n", root->data);
    printf("Left Child: %d\n", root->left->data);
    printf("Right Child: %d\n", root->right->data);

    return 0;
}

Program Output

Root: 10
Left Child: 20
Right Child: 30

Final Tree

          10
        /    \
      20      30
     /  \    /  \
   40   50  60   70

📘 Learning Note

This short program focuses on node creation and pointer connections. In long-running programs, dynamically allocated Tree nodes should also be released when no longer needed.

PROGRAM TRACING

🔎 Trace the Binary Tree Construction

COMPLEXITY + INTERVIEW NOTE

⚡ Binary Tree Basics — Complexity

Create One Node — O(1) One allocation and constant number of assignments.
Connect One Child — O(1) A left or right pointer assignment is constant time.
Build n Nodes — O(n) Creating and connecting n nodes takes linear work.
Space — O(n) Each node occupies memory for data and two pointers.

🎯 Interview Note

If the root is at depth 0, the maximum number of nodes at depth d is 2^d. A perfect Binary Tree of height h can contain 2^(h+1) - 1 nodes.

TREE TRAVERSAL

🔵 Preorder Traversal

A Tree traversal visits every node of a Tree in a systematic order. In Preorder Traversal, we process the current node before its subtrees.

1. ROOT Visit the current node first.
2. LEFT Traverse the left subtree.
3. RIGHT Traverse the right subtree.

💡 Preorder Rule

Remember it as ROOT → LEFT → RIGHT. Because the root is processed first, Preorder is useful when parent information must appear before child information.

🧠 Example Tree

          10
        /    \
      20      30
     /  \    /  \
   40   50  60   70
Preorder: 10 20 40 50 30 60 70
ALGORITHM

⚙️ Recursive Preorder Algorithm

PREORDER(root)

1. If root == NULL
      return

2. Visit root

3. PREORDER(root->left)

4. PREORDER(root->right)

🔁 Why Recursion Fits Trees

Every left or right child is itself the root of a smaller subtree. So the same Preorder logic can be applied recursively until a NULL pointer is reached.

VISUALIZER

🎬 Preorder Traversal Visualizer

INTERACTIVE ALGORITHM VISUALIZATION
CodeBhavya CodeBhavya
🎬 Premium Preorder Traversal Visualizer Follow ROOT → LEFT → RIGHT and watch the recursive traversal order build.
Current Node —
Step Type —
Visited Count 0
Root —
Traversal Output: —
Press Next to start Preorder Traversal.
C PROGRAM

💻 Recursive Preorder Traversal in C

Visible Learning Program

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

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

struct Node *createNode(int value)
{
    struct Node *newNode =
        (struct Node *)malloc(sizeof(struct Node));

    newNode->data = value;
    newNode->left = NULL;
    newNode->right = NULL;

    return newNode;
}

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

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

    preorder(root->left);
    preorder(root->right);
}

int main()
{
    struct Node *root;

    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);

    preorder(root);

    return 0;
}

Program Output

10 20 40 50 30 60 70

Traversal Rule

ROOT
LEFT subtree
RIGHT subtree
PROGRAM TRACING

🔎 Trace Recursive Preorder Execution

COMPLEXITY + INTERVIEW NOTE

⚡ Preorder Traversal Complexity

Time — O(n) Every node is visited exactly once.
Auxiliary Space — O(h) Recursion uses one call-stack frame per Tree level.
Balanced Tree — O(log n) Recursive stack height is logarithmic when the Tree is balanced.
Skewed Tree — O(n) Worst-case recursive stack depth becomes linear.

🎯 Interview Note

Preorder naturally produces a parent-before-children order. It is commonly used for copying/serializing Tree structure, prefix expression generation, and hierarchical output.

TREE TRAVERSAL

🟡 Inorder Traversal

In Inorder Traversal, we completely process the left subtree first, then visit the current node, and finally process the right subtree.

1. LEFT Traverse the left subtree.
2. ROOT Visit the current node.
3. RIGHT Traverse the right subtree.

💡 Inorder Rule

Remember it as LEFT → ROOT → RIGHT. The root is processed only after the entire left subtree has been handled.

🧠 Example Tree

          10
        /    \
      20      30
     /  \    /  \
   40   50  60   70
Inorder: 40 20 50 10 60 30 70
ALGORITHM

⚙️ Recursive Inorder Algorithm

INORDER(root)

1. If root == NULL
      return

2. INORDER(root->left)

3. Visit root

4. INORDER(root->right)

🔑 Special BST Property

For a Binary Search Tree, Inorder Traversal produces the keys in sorted ascending order. We will use this property again when we study BST.

VISUALIZER

🎬 Inorder Traversal Visualizer

INTERACTIVE ALGORITHM VISUALIZATION
CodeBhavya CodeBhavya
🎬 Premium Inorder Traversal Visualizer Follow LEFT → ROOT → RIGHT and watch the recursive output appear in exact order.
Current Node —
Step Type —
Visited Count 0
Root —
Traversal Output: —
Press Next to start Inorder Traversal.
C PROGRAM

💻 Recursive Inorder Traversal in C

Visible Learning Program

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

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

struct Node *createNode(int value)
{
    struct Node *newNode =
        (struct Node *)malloc(sizeof(struct Node));

    newNode->data = value;
    newNode->left = NULL;
    newNode->right = NULL;

    return newNode;
}

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

    inorder(root->left);

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

    inorder(root->right);
}

int main()
{
    struct Node *root;

    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);

    inorder(root);

    return 0;
}

Program Output

40 20 50 10 60 30 70

Traversal Rule

LEFT subtree
ROOT
RIGHT subtree
PROGRAM TRACING

🔎 Trace Recursive Inorder Execution

COMPLEXITY + INTERVIEW NOTE

⚡ Inorder Traversal Complexity

Time — O(n) Every node is visited exactly once.
Auxiliary Space — O(h) Recursive depth depends on Tree height.
Balanced Tree — O(log n) The recursive stack is logarithmic for a balanced Tree.
Skewed Tree — O(n) A one-sided Tree can require n recursive frames.

🎯 Interview Note

Inorder is especially important for Binary Search Trees because it visits BST keys in sorted order. For an ordinary Binary Tree, Inorder does not automatically produce sorted values.

TREE TRAVERSAL

🟣 Postorder Traversal

In Postorder Traversal, we process both subtrees before visiting the current node. That means the parent is handled only after its children are completely processed.

1. LEFT Traverse the left subtree.
2. RIGHT Traverse the right subtree.
3. ROOT Visit the current node last.

💡 Postorder Rule

Remember it as LEFT → RIGHT → ROOT. Since children are handled before their parent, Postorder is useful for deleting/freeing a Tree and for evaluating expression trees.

🧠 Example Tree

          10
        /    \
      20      30
     /  \    /  \
   40   50  60   70
Postorder: 40 50 20 60 70 30 10
ALGORITHM

⚙️ Recursive Postorder Algorithm

POSTORDER(root)

1. If root == NULL
      return

2. POSTORDER(root->left)

3. POSTORDER(root->right)

4. Visit root

🧹 Why Postorder is Good for Deleting a Tree

Before freeing a parent node, its left and right subtrees should already be processed. Postorder naturally gives exactly that children-before-parent order.

VISUALIZER

🎬 Postorder Traversal Visualizer

INTERACTIVE ALGORITHM VISUALIZATION
CodeBhavya CodeBhavya
🎬 Premium Postorder Traversal Visualizer Follow LEFT → RIGHT → ROOT and watch each parent appear only after its children.
Current Node —
Step Type —
Visited Count 0
Root —
Traversal Output: —
Press Next to start Postorder Traversal.
C PROGRAM

💻 Recursive Postorder Traversal in C

Visible Learning Program

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

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

struct Node *createNode(int value)
{
    struct Node *newNode =
        (struct Node *)malloc(sizeof(struct Node));

    newNode->data = value;
    newNode->left = NULL;
    newNode->right = NULL;

    return newNode;
}

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

    postorder(root->left);
    postorder(root->right);

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

int main()
{
    struct Node *root;

    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);

    postorder(root);

    return 0;
}

Program Output

40 50 20 60 70 30 10

Traversal Rule

LEFT subtree
RIGHT subtree
ROOT
PROGRAM TRACING

🔎 Trace Recursive Postorder Execution

COMPLEXITY + INTERVIEW NOTE

⚡ Postorder Traversal Complexity

Time — O(n) Every node is visited exactly once.
Auxiliary Space — O(h) Recursive depth depends on Tree height.
Balanced Tree — O(log n) The recursion stack is logarithmic for a balanced Tree.
Skewed Tree — O(n) A one-sided Tree can require n recursive frames.

🎯 Interview Note

Postorder is the natural traversal for freeing an entire dynamically allocated Tree: free the left subtree, free the right subtree, then free the current node.

TREE TRAVERSAL

🟢 Level Order Traversal

Level Order Traversal visits a Tree level by level from top to bottom, and from left to right within each level. It is the Tree form of Breadth-First Search (BFS).

1. ENQUEUE ROOT Start by placing the root in a Queue.
2. DEQUEUE + VISIT Remove the FRONT node and process it.
3. ENQUEUE CHILDREN Add its left child, then right child.

💡 Why a Queue?

A FIFO Queue keeps nodes in discovery order. Nodes discovered earlier are processed earlier, which naturally gives level-by-level traversal.

🧠 Example Tree

          10
        /    \
      20      30
     /  \    /  \
   40   50  60   70
Level Order: 10 20 30 40 50 60 70
ALGORITHM

⚙️ Level Order Algorithm using Queue

LEVEL_ORDER(root)

1. If root == NULL
      return

2. Create an empty Queue

3. Enqueue root

4. While Queue is not empty

      current = Dequeue()

      Visit current

      If current->left != NULL
          Enqueue current->left

      If current->right != NULL
          Enqueue current->right

🔁 BFS Connection

The same idea appears in graph BFS: discover nodes, place them in a Queue, and process them in FIFO order.

VISUALIZER

🎬 Level Order Traversal Visualizer

INTERACTIVE ALGORITHM VISUALIZATION
CodeBhavya CodeBhavya
🎬 Premium Level Order / BFS Visualizer Watch the Queue change while nodes are visited level by level.
Queue FRONT → REAR
Current Node —
Operation —
Visited Count 0
Queue Size 0
Traversal Output: —
Press Next to enqueue the root.
C PROGRAM

💻 Level Order Traversal in C

Visible Learning Program

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

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

struct Node *createNode(int value)
{
    struct Node *newNode =
        (struct Node *)malloc(sizeof(struct Node));

    newNode->data = value;
    newNode->left = NULL;
    newNode->right = NULL;

    return newNode;
}

void levelOrder(struct Node *root)
{
    struct Node *queue[100];
    int front = 0;
    int rear = 0;

    if(root == NULL)
        return;

    queue[rear++] = root;

    while(front < rear)
    {
        struct Node *current = queue[front++];

        printf("%d ", current->data);

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

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

int main()
{
    struct Node *root;

    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);

    levelOrder(root);

    return 0;
}

Program Output

10 20 30 40 50 60 70

Core Idea

Queue: FIFO

Dequeue node
Visit node
Enqueue LEFT
Enqueue RIGHT
PROGRAM TRACING

🔎 Trace Level Order Execution

COMPLEXITY + INTERVIEW NOTE

⚡ Level Order Traversal Complexity

Time — O(n) Every Tree node is enqueued, dequeued, and visited once.
Auxiliary Space — O(w) The Queue can hold up to the maximum Tree width.
Worst Case — O(n) A very wide level can contain a linear number of nodes.
No Recursion This iterative version uses a Queue instead of recursive call-stack frames.

🎯 Interview Note

Level Order Traversal is BFS on a Tree. If an interviewer asks for nodes level by level, shortest level distance from the root, or level-wise processing, think of a Queue.

BINARY SEARCH TREE

🌲 Binary Search Tree (BST)

A Binary Search Tree is a Binary Tree that maintains an ordering rule. For every node, smaller values are stored in the left subtree and larger values are stored in the right subtree.

LEFT Subtree Contains values smaller than the current node.
ROOT Separates smaller values on the left from larger values on the right.
RIGHT Subtree Contains values larger than the current node.

🧠 Example BST

          50
        /    \
      30      70
     /  \    /  \
   20   40  60   80
Inorder: 20 30 40 50 60 70 80

📌 Duplicate Policy Used Here

This learning implementation does not insert duplicate values. When value == root->data, the existing node is kept unchanged.

Binary Tree Binary Search Tree
No general ordering rule between node values. Maintains left-smaller and right-larger ordering.
Searching may require checking many or all nodes. Ordering lets Search choose only one subtree at each comparison.
Inorder is not necessarily sorted. Inorder produces ascending values for a valid BST.
BST SEARCH

🔍 Searching in a BST

BST Search compares the key with the current node and discards one entire subtree after each comparison. 

SEARCH(root, key)

1. If root == NULL
      return NOT FOUND

2. If root->data == key
      return root

3. If key < root->data
      SEARCH(root->left, key)

4. Otherwise
      SEARCH(root->right, key)

🧠 Search for 60

Start at 50. Since 60 > 50, move RIGHT to 70. Since 60 < 70, move LEFT to 60. The key is found.

Search Path: 50 → 70 → 60
BST INSERT

➕ Inserting into a BST

Insertion follows the same comparison rule as Search until an empty NULL position is found. A new node is created at that position. 

INSERT(root, value)

1. If root == NULL
      return new Node(value)

2. If value < root->data
      root->left =
          INSERT(root->left, value)

3. Else if value > root->data
      root->right =
          INSERT(root->right, value)

4. Return root

💡 Example: Insert 60

50 → go RIGHT to 70 → go LEFT because 60 < 70 → the left position is empty → insert 60 there.

VISUALIZER

🎬 BST Search & Insert Visualizer

INTERACTIVE ALGORITHM VISUALIZATION
CodeBhavya CodeBhavya
🎬 Premium BST Search & Insert Visualizer Build a BST, compare values step by step, insert new nodes, and trace a search path.
Current —
Compare —
Direction —
Nodes 0
Status Ready
Path: —
Press Next to begin.
C PROGRAM

💻 BST Insert and Search in C

Visible Learning Program

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

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

struct Node *createNode(int value)
{
    struct Node *newNode =
        (struct Node *)malloc(sizeof(struct Node));

    newNode->data = value;
    newNode->left = NULL;
    newNode->right = NULL;

    return newNode;
}

struct Node *insert(struct Node *root, int value)
{
    if(root == NULL)
        return createNode(value);

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

    return root;
}

struct Node *search(struct Node *root, int key)
{
    if(root == NULL || root->data == key)
        return root;

    if(key < root->data)
        return search(root->left, key);

    return search(root->right, key);
}

int main()
{
    struct Node *root = NULL;
    struct Node *result;

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

    result = search(root, 60);

    if(result != NULL)
        printf("60 Found\n");
    else
        printf("60 Not Found\n");

    return 0;
}

Program Output

60 Found

Final BST

          50
        /    \
      30      70
     /  \    /  \
   20   40  60   80
PROGRAM TRACING

🔎 Trace BST Insert + Search

COMPLEXITY + INTERVIEW NOTE

⚡ BST Search & Insert Complexity

Search — O(h) Each comparison moves down only one subtree.
Insert — O(h) Insertion follows one root-to-NULL path.
Balanced BST — O(log n) When height is logarithmic, Search and Insert are efficient.
Skewed BST — O(n) A badly shaped BST can behave like a linked list.

🎯 Interview Note

BST performance depends on height, not merely on the number of nodes. A balanced BST keeps height near log n; a skewed BST can have height near n.

BST DELETION

🗑️ Deleting a Node from a BST

BST deletion must remove the required key while still preserving the rule LEFT < ROOT < RIGHT. The exact action depends on how many children the node has.

💡 First Step is Always Search

Compare the key with the current node. Move LEFT for a smaller key and RIGHT for a larger key until the target node is found.

THREE DELETION CASES

🧩 The 3 Cases of BST Deletion

Case 1 — Leaf Node The node has no children. Remove it directly and return NULL to its parent.
Case 2 — One Child Replace the deleted node with its only child by returning that child pointer.
Case 3 — Two Children Copy the inorder successor value into the node, then delete that successor from the right subtree.

🧠 One Sequence Demonstrates All Three Cases

Initial BST

          50
        /    \
      30      70
     /  \    /  \
   20   40  60   80
Delete 20 → leaf case
Delete 30 → one-child case (only child 40 remains)
Delete 50 → two-child case (inorder successor = 60)
ALGORITHM

⚙️ BST Deletion Algorithm

DELETE(root, key)

1. If root == NULL
      return root

2. If key < root->data
      root->left =
          DELETE(root->left, key)

3. Else if key > root->data
      root->right =
          DELETE(root->right, key)

4. Else
      target node is found

      A. If left == NULL
            temp = right
            free(root)
            return temp

      B. If right == NULL
            temp = left
            free(root)
            return temp

      C. Otherwise
            temp =
                minimum node in right subtree

            root->data = temp->data

            root->right =
                DELETE(root->right,
                       temp->data)

5. Return root

🔑 Why the Inorder Successor?

The minimum value in the right subtree is greater than every value in the left subtree but is the smallest valid replacement larger than the current node. After copying it, we remove the original successor node from the right subtree.

VISUALIZER

🎬 BST Deletion Visualizer

INTERACTIVE ALGORITHM VISUALIZATION
CodeBhavya CodeBhavya
🎬 Premium BST Deletion Visualizer Watch leaf, one-child, and two-child deletion while the BST ordering remains valid.
Current —
Case —
Successor —
Nodes 0
Status Ready
Search / Successor Path: —
Press Next to begin BST deletion.
C PROGRAM

💻 BST Deletion in C

Visible Learning Program

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

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

struct Node *createNode(int value)
{
    struct Node *newNode =
        (struct Node *)malloc(sizeof(struct Node));

    newNode->data = value;
    newNode->left = NULL;
    newNode->right = NULL;

    return newNode;
}

struct Node *insert(struct Node *root, int value)
{
    if(root == NULL)
        return createNode(value);

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

    return root;
}

struct Node *minValueNode(struct Node *root)
{
    struct Node *current = root;

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

    return current;
}

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

    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)
        {
            temp = root->right;
            free(root);
            return temp;
        }

        if(root->right == NULL)
        {
            temp = root->left;
            free(root);
            return temp;
        }

        temp = minValueNode(root->right);

        root->data = temp->data;

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

    return root;
}

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

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

int main()
{
    struct Node *root = NULL;

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

    root = deleteNode(root, 20);
    printf("After deleting 20: ");
    inorder(root);
    printf("\n");

    root = deleteNode(root, 30);
    printf("After deleting 30: ");
    inorder(root);
    printf("\n");

    root = deleteNode(root, 50);
    printf("After deleting 50: ");
    inorder(root);
    printf("\n");

    return 0;
}

Program Output

After deleting 20: 30 40 50 60 70 80
After deleting 30: 40 50 60 70 80
After deleting 50: 40 60 70 80

Deletion Cases

20 → Leaf
30 → One Child
50 → Two Children

Successor of 50 → 60
PROGRAM TRACING

🔎 Trace All Three BST Deletion Cases

COMPLEXITY + INTERVIEW NOTE

⚡ BST Deletion Complexity

Deletion — O(h) The search path and replacement work depend on BST height.
Balanced BST — O(log n) Deletion is efficient when height remains logarithmic.
Skewed BST — O(n) Worst-case height can become linear.
Recursive Space — O(h) Recursive calls use one stack frame per level followed.

🎯 Interview Note

The difficult case is deleting a node with two children. A common solution is to replace its value with the inorder successor (minimum node in the right subtree), then recursively delete that successor.

HEAP FUNDAMENTALS

⛰️ Binary Heap

A Binary Heap is a Complete Binary Tree that also follows a heap-order property. Because it is complete, it can be stored very efficiently in an array without explicit left/right pointers.

Complete Binary Tree Every level is full except possibly the last, and the last level is filled from left to right.
Heap Order A Max Heap keeps the parent greater than or equal to its children; a Min Heap keeps it smaller.
Array Friendly The complete shape gives direct formulas for parent and child indices.

📌 Heap vs BST

A Heap guarantees only a parent-child ordering. It does not guarantee that every value in the left subtree is smaller than every value in the right subtree, so Heap Search is not the same as BST Search.

MIN HEAP & MAX HEAP

↕️ Two Basic Binary Heaps

🔵 Max Heap

For every node: Parent ≥ Children. The maximum value is always at the root. 

          50
        /    \
      30      40
     /  \    / \
   10   20  35  37

🟡 Min Heap

For every node: Parent ≤ Children. The minimum value is always at the root. 

          10
        /    \
      20      30
     /  \    / \
   40   50  35  37

🎯 Important

The root can be accessed in O(1), but inserting or deleting the root may require moving along the Tree height, which takes O(log n).

ARRAY REPRESENTATION

🧮 Heap Index Formulas

With 0-based indexing, a node stored at index i has:

Parent (i - 1) / 2
Left Child 2 * i + 1
Right Child 2 * i + 2
050
130
240
310
420
535
637
For index 2: parent = 0, left child = 5, right child = 6. So value 40 has parent 50 and children 35 and 37.
INSERTION

➕ Insert into a Max Heap

Insert the new value at the next free array position to preserve the complete-tree shape. Then compare it with its parent and swap upward until the Max Heap property is restored. This upward correction is often called heapify-up or sift-up. 

INSERT_MAX(heap, size, value)

1. Put value at heap[size]
2. size = size + 1
3. i = size - 1

4. While i > 0
      parent = (i - 1) / 2

      If heap[parent] >= heap[i]
          stop

      Swap heap[parent], heap[i]
      i = parent

🧠 Insert 45

Append 45 at index 7 → compare with parent 10 → swap → compare with parent 30 → swap → compare with 50 → stop. 
Before: 50 30 40 10 20 35 37
After : 50 45 40 30 20 35 37 10
DELETE ROOT

➖ Delete the Root of a Max Heap

The root contains the maximum element. To delete it while preserving the complete-tree shape, move the last heap element to the root, reduce the size, then restore heap order by moving downward. 

DELETE_MAX(heap, size)

1. Save heap[0]
2. Move heap[size - 1] to heap[0]
3. size = size - 1
4. HEAPIFY_DOWN(heap, size, 0)
5. Return saved maximum

💡 Why Move the Last Element?

Removing the last array element preserves the complete Binary Tree shape. Only the heap-order property may be broken, so we repair that with heapify-down.

HEAPIFY

🔧 Heapify Down

For a Max Heap, compare the current value with its children. If one child is larger, swap with the largest child and continue from that child index. 

HEAPIFY_DOWN(heap, size, i)

1. largest = i
2. left  = 2*i + 1
3. right = 2*i + 2

4. If left exists and
      heap[left] > heap[largest]
      largest = left

5. If right exists and
      heap[right] > heap[largest]
      largest = right

6. If largest == i
      stop

7. Swap heap[i], heap[largest]
8. i = largest
9. Repeat
For a Min Heap, the same idea is used with the comparisons reversed: choose the smallest child.
VISUALIZER

🎬 Binary Heap Visualizer

INTERACTIVE ALGORITHM VISUALIZATION
CodeBhavya CodeBhavya
🎬 Premium Binary Heap Visualizer Watch the same Heap as both a Complete Binary Tree and an array.
Heap Array 0-based indexing
Current Index —
Compare Index —
Operation —
Size 0
Root —
Heapify Path: —
Press Next to begin.
C PROGRAM

💻 Max Heap Insert + Delete in C

Visible Learning Program

#include <stdio.h>

#define MAX 100

void swap(int *a, int *b)
{
    int temp = *a;
    *a = *b;
    *b = temp;
}

void insertMaxHeap(int heap[], int *size, int value)
{
    int i = *size;
    int parent;

    heap[i] = value;
    (*size)++;

    while(i > 0)
    {
        parent = (i - 1) / 2;

        if(heap[parent] >= heap[i])
            break;

        swap(&heap[parent], &heap[i]);
        i = parent;
    }
}

void heapifyDown(int heap[], int size, int i)
{
    int largest;
    int left;
    int right;

    while(1)
    {
        largest = i;
        left = 2 * i + 1;
        right = 2 * i + 2;

        if(left < size && heap[left] > heap[largest])
            largest = left;

        if(right < size && heap[right] > heap[largest])
            largest = right;

        if(largest == i)
            break;

        swap(&heap[i], &heap[largest]);
        i = largest;
    }
}

int deleteMax(int heap[], int *size)
{
    int root;

    if(*size == 0)
        return -1;

    root = heap[0];

    heap[0] = heap[*size - 1];
    (*size)--;

    if(*size > 0)
        heapifyDown(heap, *size, 0);

    return root;
}

void printHeap(int heap[], int size)
{
    int i;

    for(i = 0; i < size; i++)
        printf("%d ", heap[i]);

    printf("\n");
}

int main()
{
    int heap[MAX];
    int size = 0;
    int deleted;

    insertMaxHeap(heap, &size, 50);
    insertMaxHeap(heap, &size, 30);
    insertMaxHeap(heap, &size, 40);
    insertMaxHeap(heap, &size, 10);
    insertMaxHeap(heap, &size, 20);
    insertMaxHeap(heap, &size, 35);
    insertMaxHeap(heap, &size, 37);

    printf("Initial Max Heap: ");
    printHeap(heap, size);

    insertMaxHeap(heap, &size, 45);

    printf("After inserting 45: ");
    printHeap(heap, size);

    deleted = deleteMax(heap, &size);

    printf("Deleted root: %d\n", deleted);
    printf("After deletion: ");
    printHeap(heap, size);

    return 0;
}

Program Output

Initial Max Heap: 50 30 40 10 20 35 37
After inserting 45: 50 45 40 30 20 35 37 10
Deleted root: 50
After deletion: 45 30 40 10 20 35 37

Core Operations

Insert:
append → heapify up

Delete root:
last → root
size--
heapify down
PROGRAM TRACING

🔎 Trace Max Heap Insert + Delete

COMPLEXITY + INTERVIEW NOTE

⚡ Binary Heap Complexity

Peek Root — O(1) Maximum or minimum is stored at index 0.
Insert — O(log n) A new value may move from the last level to the root.
Delete Root — O(log n) Heapify-down follows at most one root-to-leaf path.
Space — O(n) The Heap stores n elements in its array.

🎯 Interview Note

A Binary Heap is excellent when you repeatedly need the highest- or lowest-priority element. That is why it is a standard implementation of a Priority Queue. Advanced Heap families such as Binomial and Fibonacci Heaps belong in the later advanced Heap module.

IMPORTANT TREE PROBLEMS

🧠 Core Binary Tree & BST Problems

After learning traversal, BST operations, and Heap fundamentals, the next step is to solve recurring Tree interview problems. These problems strengthen recursion, subtree reasoning, height calculation, and BST ordering.

Count Problems Total nodes, leaf nodes, internal nodes, and nodes at a level.
Structure Problems Height, mirror, identical Trees, balance, and diameter.
Search Problems Binary Tree search, LCA, BST min/max, predecessor, and successor.

🎯 How to Think About Tree Problems

For many recursive Tree questions, first solve the same problem for the LEFT subtree, then for the RIGHT subtree, and finally combine those two answers at the current node.

COUNT + HEIGHT

🔢 Count Nodes, Leaves, Internal Nodes & Height

Total Nodes

COUNT(root)

if root == NULL
    return 0

return 1
       + COUNT(root->left)
       + COUNT(root->right)

Leaf Nodes

LEAVES(root)

if root == NULL
    return 0

if left == NULL
   and right == NULL
    return 1

return LEAVES(left)
       + LEAVES(right)

Internal Nodes

internal =
    totalNodes - leafNodes

For a non-empty Tree, internal nodes are the nodes having at least one child.

Tree Height

HEIGHT(root)

if root == NULL
    return 0

return 1 +
       max(HEIGHT(left),
           HEIGHT(right))

🧠 Fixed Example

          10
        /    \
      20      30
     /  \    /  \
   40   50  60   70
Total Nodes = 7
Leaf Nodes = 4
Internal Nodes = 3
Height = 3 levels = 2 edges

📌 Height Convention

Our C program returns height as the number of levels / nodes on the longest path. Some textbooks define height as the number of edges instead. Under that convention, this Tree has height 2.

BINARY TREE SEARCH

🔍 Search an Ordinary Binary Tree

Unlike a BST, an ordinary Binary Tree has no ordering rule. So in the worst case we may need to examine every node. 

SEARCH(root, key)

1. If root == NULL
      return false

2. If root->data == key
      return true

3. If SEARCH(root->left, key)
      return true

4. Return
      SEARCH(root->right, key)
Search 60 in the fixed Tree → Found
MIRROR TREE

🪞 Mirror a Binary Tree

To mirror a Binary Tree, swap the LEFT and RIGHT child pointers at every node. 

void mirror(struct Node *root)
{
    struct Node *temp;

    if(root == NULL)
        return;

    temp = root->left;
    root->left = root->right;
    root->right = temp;

    mirror(root->left);
    mirror(root->right);
}

Before

      10
     /  \
   20    30

After Mirror

      10
     /  \
   30    20
IDENTICAL TREES

👯 Check Whether Two Trees are Identical

Two Trees are identical when they have the same structure and the same data at corresponding nodes. 

int identical(struct Node *a, struct Node *b)
{
    if(a == NULL && b == NULL)
        return 1;

    if(a == NULL || b == NULL)
        return 0;

    return a->data == b->data &&
           identical(a->left, b->left) &&
           identical(a->right, b->right);
}

💡 Recursive Condition

Current values must match, LEFT subtrees must be identical, and RIGHT subtrees must be identical.

BALANCED TREE

⚖️ Check Whether a Binary Tree is Height-Balanced

A Binary Tree is height-balanced when, at every node, the height difference between the LEFT and RIGHT subtrees is at most 1. 

int checkHeight(struct Node *root)
{
    int leftHeight;
    int rightHeight;

    if(root == NULL)
        return 0;

    leftHeight = checkHeight(root->left);
    if(leftHeight == -1)
        return -1;

    rightHeight = checkHeight(root->right);
    if(rightHeight == -1)
        return -1;

    if(abs(leftHeight - rightHeight) > 1)
        return -1;

    return 1 + (leftHeight > rightHeight
                ? leftHeight : rightHeight);
}

/* Balanced when checkHeight(root) != -1 */

🎯 Interview Improvement

Computing height separately at every node can become O(n²). Returning -1 immediately when an unbalanced subtree is detected allows an O(n) solution.

TREE DIAMETER

📏 Diameter of a Binary Tree

The diameter is the number of nodes (or sometimes edges, depending on convention) on the longest path between any two nodes. That longest path may or may not pass through the root. 

int diameterHeight(struct Node *root, int *diameter)
{
    int leftHeight;
    int rightHeight;

    if(root == NULL)
        return 0;

    leftHeight = diameterHeight(root->left, diameter);
    rightHeight = diameterHeight(root->right, diameter);

    if(leftHeight + rightHeight + 1 > *diameter)
        *diameter = leftHeight + rightHeight + 1;

    return 1 + (leftHeight > rightHeight
                ? leftHeight : rightHeight);
}
At each node, candidate diameter in nodes = leftHeight + rightHeight + 1
LOWEST COMMON ANCESTOR

🌿 Lowest Common Ancestor (LCA)

The Lowest Common Ancestor of two nodes is the lowest node in the Tree that has both target nodes in its subtree, allowing a node to be an ancestor of itself. 

struct Node *lca(struct Node *root, int a, int b)
{
    struct Node *left;
    struct Node *right;

    if(root == NULL ||
       root->data == a ||
       root->data == b)
        return root;

    left = lca(root->left, a, b);
    right = lca(root->right, a, b);

    if(left != NULL && right != NULL)
        return root;

    return left != NULL ? left : right;
}

Example

In the fixed Tree, LCA(40, 50) = 20 and LCA(40, 60) = 10.

BST MIN / MAX

↔️ Find Minimum and Maximum in a BST

BST ordering makes these operations very simple: keep moving LEFT for the minimum and RIGHT for the maximum. 

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

    while(root->left != NULL)
        root = root->left;

    return root;
}

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

    while(root->right != NULL)
        root = root->right;

    return root;
}
Time = O(h), where h is BST height.
BST PREDECESSOR / SUCCESSOR

⏮️ Predecessor & Successor in a BST

For a key in sorted BST order, the predecessor is the largest smaller key and the successor is the smallest larger key. 

void predecessorSuccessor(
    struct Node *root,
    int key,
    struct Node **pred,
    struct Node **succ)
{
    while(root != NULL)
    {
        if(key < root->data)
        {
            *succ = root;
            root = root->left;
        }
        else if(key > root->data)
        {
            *pred = root;
            root = root->right;
        }
        else
        {
            if(root->left != NULL)
                *pred = bstMax(root->left);

            if(root->right != NULL)
                *succ = bstMin(root->right);

            return;
        }
    }
}

📌 Core Rule

If the target has a LEFT subtree, its predecessor is the maximum of that subtree. If it has a RIGHT subtree, its successor is the minimum of that subtree. Ancestors encountered during search handle the remaining cases.

VISUALIZER

🎬 Important Tree Problems Visualizer

INTERACTIVE ALGORITHM VISUALIZATION
CodeBhavya CodeBhavya
🎬 Premium Tree Problems Lab Count nodes, count leaves, measure height, search, or mirror the same Binary Tree.
Current Node —
Operation —
Partial Result —
Visited 0
Final Result —
Details: —
Press Next to begin.
C PROGRAM

💻 Core Recursive Tree Problems in C

This learning program combines four core problems in one place: count total nodes, count leaf nodes, find height, and search an ordinary Binary Tree.

Visible Learning Program

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

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

struct Node *createNode(int value)
{
    struct Node *newNode =
        (struct Node *)malloc(sizeof(struct Node));

    newNode->data = value;
    newNode->left = NULL;
    newNode->right = NULL;

    return newNode;
}

int countNodes(struct Node *root)
{
    int leftCount;
    int rightCount;

    if(root == NULL)
        return 0;

    leftCount = countNodes(root->left);
    rightCount = countNodes(root->right);

    return 1 + leftCount + rightCount;
}

int countLeaves(struct Node *root)
{
    int leftLeaves;
    int rightLeaves;

    if(root == NULL)
        return 0;

    if(root->left == NULL && root->right == NULL)
        return 1;

    leftLeaves = countLeaves(root->left);
    rightLeaves = countLeaves(root->right);

    return leftLeaves + rightLeaves;
}

int treeHeight(struct Node *root)
{
    int leftHeight;
    int rightHeight;

    if(root == NULL)
        return 0;

    leftHeight = treeHeight(root->left);
    rightHeight = treeHeight(root->right);

    if(leftHeight > rightHeight)
        return leftHeight + 1;

    return rightHeight + 1;
}

int searchTree(struct Node *root, int key)
{
    if(root == NULL)
        return 0;

    if(root->data == key)
        return 1;

    if(searchTree(root->left, key))
        return 1;

    return searchTree(root->right, key);
}

int main()
{
    struct Node *root;
    int total;
    int leaves;
    int h;

    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);

    total = countNodes(root);
    leaves = countLeaves(root);
    h = treeHeight(root);

    printf("Total Nodes: %d\n", total);
    printf("Leaf Nodes: %d\n", leaves);
    printf("Internal Nodes: %d\n", total - leaves);
    printf("Height (levels): %d\n", h);

    if(searchTree(root, 60))
        printf("60 Found\n");
    else
        printf("60 Not Found\n");

    return 0;
}

Program Output

Total Nodes: 7
Leaf Nodes: 4
Internal Nodes: 3
Height (levels): 3
60 Found

Fixed Tree

          10
        /    \
      20      30
     /  \    /  \
   40   50  60   70
PROGRAM TRACING

🔎 Trace Core Recursive Tree Problems

COMPLEXITY SUMMARY

⚡ Important Tree Problems — Complexity

Problem Time Auxiliary Space Reason
Count Nodes / Leaves O(n) O(h) Visit each node once; recursion follows Tree height.
Tree Height O(n) O(h) Both subtrees may be examined.
Binary Tree Search O(n) O(h) No ordering lets us discard a subtree safely.
Mirror / Identical O(n) O(h) Each corresponding node is processed once.
Balanced Check O(n) O(h) Optimized postorder computes height while checking balance.
Diameter O(n) O(h) Optimized version computes height and diameter together.
LCA in Binary Tree O(n) O(h) May need to search both subtrees.
BST Min / Max O(h) O(1) iterative Follow only one extreme path.
BST Predecessor / Successor O(h) O(1) iterative Follow one search path plus an extreme subtree path.

🎯 Interview Note

The most common optimization pattern in Tree interviews is to avoid recomputing subtree information. For balance and diameter, calculate height while returning from the same recursion instead of running a separate height function again and again.

FINAL COMPARISON

🌳 Binary Tree vs BST vs Binary Heap

These three structures are all tree-based, but they solve different problems. Choosing the correct structure is more important than simply knowing their definitions.

Property Binary Tree Binary Search Tree Binary Heap
Shape Each node has at most two children. No general shape restriction. Binary Tree shape; may become balanced or skewed. Must be a Complete Binary Tree.
Ordering No general key-ordering rule. LEFT < ROOT < RIGHT under the duplicate policy. Parent-child priority only: Max Heap or Min Heap.
Search arbitrary key O(n) worst case. O(h): O(log n) balanced, O(n) skewed. O(n) worst case because Heap order is not a BST order.
Insert Depends on the required Tree rule. O(h). O(log n) using heapify-up.
Delete Depends on the application. O(h), with 0/1/2-child cases. Delete root in O(log n) using heapify-down.
Important traversal Preorder, Inorder, Postorder, Level Order. Inorder produces sorted keys. Array / Level Order represents the complete shape naturally.
Root significance Represents the top of the hierarchy. Splits smaller and larger search regions. Stores the maximum or minimum priority.
Typical use Hierarchies, expression trees, recursive structure problems. Ordered search, sets/maps, predecessor/successor. Priority Queues, Heap Sort, scheduling, graph algorithms.
Choose Binary Tree When the problem is primarily about hierarchy, structure, recursion, or general parent-child relationships.
Choose BST When ordered searching and sorted-key operations are important.
Choose Heap When repeatedly accessing and removing the highest- or lowest-priority element is the main requirement.

🎯 Placement Shortcut

Need ordered search? Think BST. Need highest/lowest priority quickly? Think Heap. Need a general hierarchical structure? Think Binary Tree.

INTERVIEW

❓ Tree Interview Questions — Final Revision (40 Questions)

1. What is the difference between a linear data structure and a Tree?
A linear structure organizes elements in a sequence, while a Tree organizes nodes hierarchically using parent-child relationships.
Interview answer: Linear structures are sequential; Trees are hierarchical and non-linear.
2. What is a Binary Tree?
A Binary Tree is a Tree in which every node has at most two children, called the left child and right child.
Interview answer: A Binary Tree allows 0, 1, or 2 children per node.
3. What is the difference between depth and height?
Depth measures the number of edges from the root to a node. Height measures the longest number of edges from a node down to a leaf.
Interview answer: Depth looks upward toward the root; height looks downward toward the deepest leaf.
4. What is the order of Preorder Traversal?
Preorder visits the current node first, then traverses the left subtree, and finally traverses the right subtree.
Interview answer: ROOT → LEFT → RIGHT.
5. What is the time complexity of Preorder Traversal?
Every node is processed once, so Preorder takes O(n) time for a Tree containing n nodes.
Interview answer: O(n).
6. What is the recursion-space complexity of Preorder Traversal?
The recursive call stack uses O(h) auxiliary space, where h is the Tree height. It is O(log n) for a balanced Tree and O(n) for a completely skewed Tree.
Interview answer: O(h) auxiliary recursion space.
7. What is the order of Inorder Traversal?
Inorder first traverses the left subtree, then visits the current node, and finally traverses the right subtree.
Interview answer: LEFT → ROOT → RIGHT.
8. What special result does Inorder Traversal give for a BST?
For a Binary Search Tree, Inorder Traversal visits keys in ascending sorted order when the BST uses the standard left-smaller and right-larger rule.
Interview answer: Inorder of a BST gives sorted ascending keys.
9. Does Inorder Traversal always produce sorted output?
No. Sorted output is a property of Inorder Traversal on a valid Binary Search Tree, not on every Binary Tree.
Interview answer: No—only a BST guarantees sorted Inorder output.
10. What is the order of Postorder Traversal?
Postorder first traverses the left subtree, then the right subtree, and visits the current node last.
Interview answer: LEFT → RIGHT → ROOT.
11. Why is Postorder suitable for deleting a Tree?
Postorder processes both children before their parent, so child nodes can be freed before the parent node that points to them is freed.
Interview answer: Children are handled before the parent, preventing the parent from being freed too early.
12. Where is Postorder commonly used besides deleting a Tree?
Postorder is commonly used to evaluate expression trees because operands/subexpressions are evaluated before applying the operator stored at the parent node.
Interview answer: Expression-tree evaluation is a classic Postorder application.
13. Which data structure is used for Level Order Traversal?
A FIFO Queue is used. The root is enqueued first, then each visited node's children are enqueued from left to right.
Interview answer: Level Order Traversal uses a Queue.
14. Is Level Order Traversal DFS or BFS?
It is Breadth-First Search because it processes all nodes at one level before moving to the next level.
Interview answer: Level Order is BFS.
15. What is the auxiliary-space complexity of Level Order Traversal?
The Queue requires O(w) auxiliary space, where w is the maximum number of nodes stored at one time, usually related to the maximum Tree width.
Interview answer: O(w), which is O(n) in the worst case.
16. What is the defining ordering property of a BST?
For each node, keys in the left subtree are smaller and keys in the right subtree are larger, according to the duplicate policy used by the implementation.
Interview answer: LEFT < ROOT < RIGHT.
17. What is the time complexity of Search and Insert in a BST?
Both operations take O(h), where h is Tree height. That becomes O(log n) for a balanced BST and O(n) for a skewed BST.
Interview answer: O(h): O(log n) balanced, O(n) worst case.
18. Why does Inorder Traversal of a BST produce sorted output?
Inorder visits LEFT subtree, then ROOT, then RIGHT subtree. Because every left key is smaller and every right key is larger, the keys appear in ascending order.
Interview answer: Inorder follows the BST ordering from smaller to larger keys.
19. What are the three cases in BST deletion?
The target can be a leaf, a node with one child, or a node with two children. Each case reconnects the BST differently.
Interview answer: 0 children, 1 child, or 2 children.
20. How do you delete a BST node with two children?
A standard approach copies the inorder successor value into the target node, then recursively deletes the original successor from the right subtree.
Interview answer: Replace with the minimum of the right subtree, then delete that successor.
21. What is the time complexity of BST deletion?
Deletion takes O(h), where h is Tree height. That is O(log n) for a balanced BST and O(n) in the worst-case skewed BST.
Interview answer: O(h).
22. What two properties define a Binary Heap?
A Binary Heap must be a Complete Binary Tree and must satisfy either the Max Heap or Min Heap parent-child ordering rule.
Interview answer: Complete-tree shape + heap-order property.
23. What are the 0-based array formulas for a Heap?
For index i, parent is (i-1)/2 using integer division, left child is 2i+1, and right child is 2i+2.
Interview answer: Parent=(i−1)/2, Left=2i+1, Right=2i+2.
24. Why is Heap insertion O(log n)?
The new element is appended at the last position and may move upward through at most the height of the Complete Binary Tree, which is O(log n).
Interview answer: Heapify-up follows at most one root-to-leaf height in reverse.
25. What is the main difference between a BST and a Heap?
A BST maintains a global left-smaller/right-larger search ordering, while a Heap guarantees only parent-child priority ordering and keeps the Tree complete.
Interview answer: BST is optimized for ordered search; Heap is optimized for root priority.
26. How do you count total nodes in a Binary Tree recursively?
Return 0 for NULL. Otherwise return 1 plus the node counts of the LEFT and RIGHT subtrees.
Interview answer: 1 + count(left) + count(right).
27. What is the difference between Tree height measured in nodes and edges?
If the longest root-to-leaf path contains k nodes, its length is k−1 edges. Both conventions are used, so state which definition your solution follows.
Interview answer: Edge-height is one less than node/level height for a non-empty Tree.
28. Why is ordinary Binary Tree search O(n) in the worst case?
An ordinary Binary Tree has no key-ordering rule, so a comparison does not tell us which subtree can be discarded.
Interview answer: Without ordering, we may need to inspect every node.
29. How can a balanced-Tree check be improved from O(n²) to O(n)?
Compute height and balance together in one postorder traversal. Return a special failure value such as −1 as soon as an unbalanced subtree is detected.
Interview answer: Combine height computation and balance checking in one recursion.
30. Does the longest Tree diameter always pass through the root?
No. The longest path may lie completely inside the LEFT or RIGHT subtree. An optimized solution updates the best diameter at every node.
Interview answer: No—the diameter can be entirely inside one subtree.
31. What is the Lowest Common Ancestor of two nodes?
It is the lowest node that has both target nodes in its subtree, where a node may be considered an ancestor of itself.
Interview answer: The deepest common ancestor of both targets.
32. How do you find minimum and maximum values in a BST?
Follow LEFT pointers until NULL for the minimum and RIGHT pointers until NULL for the maximum.
Interview answer: Leftmost node = minimum; rightmost node = maximum.
33. What is the difference between full, complete, and perfect Binary Trees?
A full Binary Tree gives every node either 0 or 2 children. A complete Binary Tree fills every level except possibly the last, which is filled left to right. A perfect Binary Tree has every internal node with two children and all leaves at the same level.
Interview answer: Full concerns child count, complete concerns filling order, perfect satisfies both complete levels and equal leaf depth.
34. Why does Level Order Traversal use a Queue?
A FIFO Queue processes nodes in the same order in which they are discovered, so all nodes at one level are processed before nodes discovered for the next level.
Interview answer: FIFO ordering naturally produces BFS / level-by-level processing.
35. When would you choose a BST instead of a Heap?
Choose a BST when you need ordered search, predecessor/successor, range-style operations, or sorted traversal. A Heap is better when root priority is the main operation.
Interview answer: BST for ordered search; Heap for repeated min/max priority.
36. Can a Binary Heap search for an arbitrary key in O(log n)?
No. Heap order only relates parents to children; it does not tell us which subtree contains an arbitrary key. An arbitrary search can therefore require O(n).
Interview answer: No—arbitrary Heap search is O(n) in the worst case.
37. What do predecessor and successor mean in a BST?
The predecessor is the greatest key smaller than the target, and the successor is the smallest key larger than the target.
Interview answer: Previous and next keys in sorted BST order.
38. Why is the two-child BST deletion case more complex?
Removing the node directly would disconnect two subtrees. A standard solution replaces its value using the inorder successor or predecessor, then removes that replacement node from its original position.
Interview answer: Two subtrees must remain ordered and connected after deletion.
39. Why is Tree height critical to ordinary BST performance?
Search, insertion, and deletion follow root-to-descendant paths, so they take O(h). A balanced BST keeps h near log n, while a skewed BST can make h near n.
Interview answer: BST operations are O(h), so smaller height means faster operations.
40. What auxiliary space do recursive Tree traversals use?
The recursive Call Stack can contain one frame per Tree level along the active path, so auxiliary space is O(h): O(log n) for a balanced Tree and O(n) for a skewed Tree.
Interview answer: O(h) recursive stack space.
PRACTICE

🎯 20 Tree Practice Problems

Try every problem yourself first. Use Solve It Yourself to write and test your C program. Open Hint only when necessary, and use Show Program when you want to study the complete official solution.

📈 Tree Practice Progress
Solved 0 / 20
Completed with Solution 0
Total Score 0 / 2000
Completion 0%
Practice Badge 🌱 Starter

🏆 Scoring

Each problem contains 5 tests × 20 points = 100 points. Passing all tests without help can earn the full score. Opening a Hint caps the competitive score for that problem at 90. After opening Show Program, you can still complete the problem, but it is recorded as Completed rather than a new competitive solve.

🌳 Practice Coverage

The 20 problems cover traversals, node counting, height, Binary Tree search, mirror/identical/balance/diameter/LCA, BST insert/search/min-max/deletion/predecessor-successor, and Binary Max Heap operations.

← Previous Topic: Queue Next Topic: Graphs →