BST Inorder Successor in DSA C - Build from Scratch

BST Inorder Successor

📖 Scenario: You are working with a Binary Search Tree (BST) that stores unique integer values. You want to find the inorder successor of a given node. The inorder successor of a node is the node with the smallest key greater than the given node's key.Think of the BST as a sorted list of numbers arranged in a tree form. Finding the inorder successor is like finding the next bigger number after a given number in this sorted list.

🎯 Goal: Build a program that creates a BST with specific nodes, sets a target node value, finds the inorder successor of that node, and prints the successor's value.

📋 What You'll Learn

Create a BST by inserting nodes with these exact values in order: 20, 9, 25, 5, 12, 11, 14

Create a variable called target and set it to 9

Implement a function inorderSuccessor that finds the inorder successor of the node with value target

Print the value of the inorder successor node

💡 Why This Matters

🌍 Real World

Finding the inorder successor is useful in database indexing, scheduling tasks in order, and navigating sorted data efficiently.

💼 Career

Understanding BST operations like inorder successor is important for software engineers working with search trees, databases, and optimization problems.

1

Create the BST with given nodes

Create a struct Node with int val, Node *left, and Node *right. Then create a function newNode that returns a new node with given value. Finally, create the BST by inserting nodes with values 20, 9, 25, 5, 12, 11, and 14 in that order using a function insert.

DSA C

# Define struct Node
// Define newNode function
// Define insert function
// Create root and insert nodes 20, 9, 25, 5, 12, 11, 14

Hint

Start by defining the Node structure and helper functions to create and insert nodes. Insert nodes in the given order to build the BST.

2

Set the target node value

Create an integer variable called target and set it to 9.

DSA C

#include 
#include 

typedef struct Node {
    int val;
    struct Node *left, *right;
} Node;

Node* newNode(int val) {
    Node* node = (Node*)malloc(sizeof(Node));
    node->val = val;
    node->left = node->right = NULL;
    return node;
}

Node* insert(Node* root, int val) {
    if (root == NULL) return newNode(val);
    if (val val) root->left = insert(root->left, val);
    else root->right = insert(root->right, val);
    return root;
}

int main() {
    Node* root = NULL;
    root = insert(root, 20);
    root = insert(root, 9);
    root = insert(root, 25);
    root = insert(root, 5);
    root = insert(root, 12);
    root = insert(root, 11);
    root = insert(root, 14);
    
    // Create target variable and set to 9
    // Your code here

    return 0;
}

Hint

Just create an integer variable named target and assign it the value 9.

3

Implement the inorderSuccessor function

Implement a function inorderSuccessor that takes Node* root and Node* p and returns the inorder successor node of p in the BST. Use the BST property to find the successor efficiently.

DSA C

#include 
#include 

typedef struct Node {
    int val;
    struct Node *left, *right;
} Node;

Node* newNode(int val) {
    Node* node = (Node*)malloc(sizeof(Node));
    node->val = val;
    node->left = node->right = NULL;
    return node;
}

Node* insert(Node* root, int val) {
    if (root == NULL) return newNode(val);
    if (val val) root->left = insert(root->left, val);
    else root->right = insert(root->right, val);
    return root;
}

Node* inorderSuccessor(Node* root, Node* p) {
    // Implement inorderSuccessor function here
    // Your code here
}

Node* findNode(Node* root, int val) {
    if (root == NULL) return NULL;
    if (val == root->val) return root;
    else if (val val) return findNode(root->left, val);
    else return findNode(root->right, val);
}

int main() {
    Node* root = NULL;
    root = insert(root, 20);
    root = insert(root, 9);
    root = insert(root, 25);
    root = insert(root, 5);
    root = insert(root, 12);
    root = insert(root, 11);
    root = insert(root, 14);
    
    int target = 9;
    Node* p = findNode(root, target);

    // Your code here

    return 0;
}

Hint

Use a loop starting from root. If p->val is less than root->val, update successor to root and go left. Otherwise, go right. Return successor at the end.

4

Print the inorder successor value

Print the value of the inorder successor node using printf. If the successor is NULL, print -1.

DSA C

#include 
#include 

typedef struct Node {
    int val;
    struct Node *left, *right;
} Node;

Node* newNode(int val) {
    Node* node = (Node*)malloc(sizeof(Node));
    node->val = val;
    node->left = node->right = NULL;
    return node;
}

Node* insert(Node* root, int val) {
    if (root == NULL) return newNode(val);
    if (val val) root->left = insert(root->left, val);
    else root->right = insert(root->right, val);
    return root;
}

Node* inorderSuccessor(Node* root, Node* p) {
    Node* successor = NULL;
    while (root != NULL) {
        if (p->val val) {
            successor = root;
            root = root->left;
        } else {
            root = root->right;
        }
    }
    return successor;
}

Node* findNode(Node* root, int val) {
    if (root == NULL) return NULL;
    if (val == root->val) return root;
    else if (val val) return findNode(root->left, val);
    else return findNode(root->right, val);
}

int main() {
    Node* root = NULL;
    root = insert(root, 20);
    root = insert(root, 9);
    root = insert(root, 25);
    root = insert(root, 5);
    root = insert(root, 12);
    root = insert(root, 11);
    root = insert(root, 14);
    
    int target = 9;
    Node* p = findNode(root, target);

    Node* succ = inorderSuccessor(root, p);

    // Print successor value or -1 if NULL
    // Your code here

    return 0;
}

Hint

Use printf to print succ->val if succ is not NULL. Otherwise, print -1.

Practice

1. What is the inorder successor of a node in a Binary Search Tree (BST)?

easy

A. The node with the largest key smaller than the given node's key

B. The node with the smallest key greater than the given node's key

C. The left child of the given node

D. The right child of the given node

Solution

1. Step 1: Understand inorder traversal in BST

   Inorder traversal visits nodes in ascending order of their keys.

2. Step 2: Define inorder successor

   The inorder successor of a node is the next node visited after it in inorder traversal, which is the smallest node greater than it.

3. Final Answer:

   The node with the smallest key greater than the given node's key -> Option B

4. Quick Check:

   Inorder successor = next bigger node [OK]

Hint: Inorder successor is next bigger node in sorted order [OK]

Common Mistakes:

• Confusing successor with predecessor
• Thinking successor is always right child
• Assuming successor is left child

2. Which of the following C function signatures correctly represents a function to find the inorder successor of a BST node?

easy

A. struct Node* inorderSuccessor(struct Node* root, struct Node* n);

B. int inorderSuccessor(int root, int n);

C. void inorderSuccessor(struct Node* root);

D. struct Node inorderSuccessor(struct Node n);

Solution

1. Step 1: Analyze function parameters

   The function needs the BST root and the node to find successor for, both as pointers.

2. Step 2: Analyze return type

   It should return a pointer to the successor node, so return type is struct Node*.

3. Final Answer:

   struct Node* inorderSuccessor(struct Node* root, struct Node* n); -> Option A

4. Quick Check:

   Correct signature uses pointers for nodes [OK]

Hint: Use pointers for nodes and return pointer to successor [OK]

Common Mistakes:

• Using int instead of struct Node*
• Missing node parameter
• Returning struct Node by value

3. Given the BST below and the node with value 15, what is the inorder successor?

        20
       /  \
     10    30
       \     \
       15    40

medium

A. 10

B. 30

C. 20

D. 40

Solution

1. Step 1: Locate node 15 and find its right subtree

   Node 15 has no right child, so successor is an ancestor.

2. Step 2: Move up to find the lowest ancestor greater than 15

   Parent 10 is less than 15, move up to 20 which is greater than 15.

3. Final Answer:

   20 -> Option C

4. Quick Check:

   Next bigger after 15 is 20 [OK]

Hint: If no right child, successor is nearest bigger ancestor [OK]

Common Mistakes:

• Choosing right child 30 incorrectly
• Choosing smaller ancestor 10
• Confusing successor with predecessor

4. Consider this buggy C code snippet to find the inorder successor of a node in BST:

struct Node* inorderSuccessor(struct Node* root, struct Node* n) {
    if (n->right != NULL) {
        struct Node* temp = n->right;
        while (temp->left != NULL) {
            temp = temp->left;
        }
        return temp;
    }
    struct Node* succ = NULL;
    while (root != NULL) {
        if (n->data < root->data) {
            succ = root;
            root = root->left;
        } else {
            root = root->right;
        }
    }
    return succ;
}

What is the main logical error in this code?

medium

A. It incorrectly updates successor when moving right

B. It returns the wrong node when node has right child

C. It uses a while loop instead of recursion

D. It does not handle the case when node has no right child

Solution

1. Step 1: Check handling of right child

   Code correctly finds leftmost node in right subtree if right child exists.

2. Step 2: Check updating successor when moving right

   In the else branch (n->data >= root->data), it incorrectly sets succ = root before moving right. Successor should NOT be updated when going right, as n is in (or at) the right subtree.

3. Step 3: Identify error

   The main logical error is incorrectly updating the successor when traversing right.

4. Final Answer:

   It incorrectly updates successor when moving right -> Option A

5. Quick Check:

   Successor updates only on left moves [OK]

Hint: Successor updates only when moving left in BST [OK]

Common Mistakes:

• Thinking recursion is required
• Updating successor when moving right
• Ignoring right subtree case

5. You have a BST and want to find the inorder successor of the node with value 25. The BST is:

         20
        /  \
      10    30
     /  \  /  \
    5  15 25  40

If the node with value 25 has no right child, what is the inorder successor and why?

hard

A. 20, because it is the root

B. 40, because it is the right child of 30

C. No successor, because 25 has no right child

D. 30, because it is the lowest ancestor greater than 25

Solution

1. Step 1: Check if node 25 has right child

   Node 25 has no right child, so successor is an ancestor.

2. Step 2: Find lowest ancestor greater than 25

   Ancestor 30 is greater than 25 and is the lowest such ancestor.

3. Final Answer:

   30, because it is the lowest ancestor greater than 25 -> Option D

4. Quick Check:

   Successor = nearest bigger ancestor [OK]

Hint: If no right child, successor is nearest bigger ancestor [OK]

Common Mistakes:

• Choosing right child 40 incorrectly
• Saying no successor exists
• Choosing root 20 incorrectly