BST Inorder Successor in DSA C

Mental Model

The inorder successor of a node in a BST is the next node in sorted order. It is the smallest node bigger than the given node.

Analogy: Imagine a line of people sorted by height. The inorder successor is the next taller person standing right after you.

       20
      /  \
    10    30
      \     \
      15    40

Node: 15
Inorder Successor: 20

Dry Run Walkthrough

Input: BST: 20 -> 10 -> 30 -> 15 -> 40, find inorder successor of 15

Goal: Find the node that comes right after 15 in sorted order

Step 1: Check if node 15 has right child

Node 15 -> right child null

Why: If right child exists, successor is leftmost node in right subtree

Step 2: Since no right child, move up to parent nodes to find a node greater than 15

Current node 15, parent 10, grandparent 20

Why: Successor is the lowest ancestor whose left child is also ancestor of node

Step 3: 15 is right child of 10, move up to 20

At node 20

Why: 20 is greater than 15 and is the first such ancestor

Result:

Inorder Successor of 15 is 20

Annotated Code

DSA C

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

// BST node structure
typedef struct Node {
    int val;
    struct Node* left;
    struct Node* right;
    struct Node* parent;
} Node;

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

// Insert node in BST with parent pointer
Node* insert(Node* root, int val, Node* parent) {
    if (root == NULL) return newNode(val, parent);
    if (val < root->val) root->left = insert(root->left, val, root);
    else root->right = insert(root->right, val, root);
    return root;
}

// Find leftmost node in subtree
Node* leftmost(Node* node) {
    while (node && node->left != NULL) {
        node = node->left; // move left to find smallest
    }
    return node;
}

// Find inorder successor of given node
Node* inorderSuccessor(Node* node) {
    if (node == NULL) return NULL;
    // Case 1: right child exists
    if (node->right != NULL) {
        return leftmost(node->right); // successor is leftmost in right subtree
    }
    // Case 2: no right child, go up to parent
    Node* p = node->parent;
    while (p != NULL && node == p->right) {
        node = p; // move up
        p = p->parent;
    }
    return p; // first parent where node is in left subtree
}

// Find node with given value
Node* findNode(Node* root, int val) {
    if (root == NULL) return NULL;
    if (val == root->val) return root;
    if (val < root->val) return findNode(root->left, val);
    else return findNode(root->right, val);
}

// Print result
void printSuccessor(Node* root, int val) {
    Node* node = findNode(root, val);
    if (node == NULL) {
        printf("Node %d not found\n", val);
        return;
    }
    Node* succ = inorderSuccessor(node);
    if (succ != NULL) {
        printf("Inorder Successor of %d is %d\n", val, succ->val);
    } else {
        printf("Inorder Successor of %d does not exist\n", val);
    }
}

int main() {
    Node* root = NULL;
    root = insert(root, 20, NULL);
    root = insert(root, 10, NULL);
    root = insert(root, 30, NULL);
    root = insert(root, 15, NULL);
    root = insert(root, 40, NULL);

    printSuccessor(root, 15);
    return 0;
}

if (node->right != NULL) { return leftmost(node->right); }

If right child exists, successor is leftmost node in right subtree

while (p != NULL && node == p->right) { node = p; p = p->parent; }

Move up to find first ancestor where node is in left subtree

return p;

Return that ancestor as successor or NULL if none

Output

Inorder Successor of 15 is 20

Complexity Analysis

Time: O(h) where h is tree height because we traverse up or down along the tree path

Space: O(1) no extra space besides pointers used

vs Alternative: Naive approach would do inorder traversal of whole tree O(n), this uses BST property to find successor in O(h)

Edge Cases

Node has right subtree

Successor is leftmost node in right subtree

DSA C

if (node->right != NULL) { return leftmost(node->right); }

Node has no right subtree and is left child

Successor is parent node

DSA C

while (p != NULL && node == p->right) { node = p; p = p->parent; }

Node is the largest node (no successor)

Function returns NULL

DSA C

return p;

Node not found in tree

Prints node not found message

DSA C

if (node == NULL) { printf("Node %d not found\n", val); return; }

When to Use This Pattern

When asked for the next bigger element in a BST, use inorder successor logic because it finds the next node in sorted order efficiently.

Common Mistakes

Mistake: Not handling the case when node has no right child and climbing up incorrectly
Fix: Use parent pointers and move up until node is left child of its parent

Mistake: Assuming successor is always right child
Fix: Check if right child exists; if not, climb up to find correct ancestor

Summary

Finds the next bigger node in BST after a given node.

Use when you need the next element in sorted order in a BST.

If right child exists, successor is leftmost in right subtree; else climb up to find first ancestor where node is in left subtree.

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