BST Inorder Successor in DSA C - Deep Dive

Overview - BST Inorder Successor

What is it?

A Binary Search Tree (BST) is a tree where each node has at most two children, and the left child's value is less than the parent's, while the right child's value is greater. The inorder successor of a node in a BST is the node that comes immediately after it when the tree is traversed in order (left, root, right). Finding the inorder successor helps in many tasks like deleting nodes or navigating the tree in sorted order.

Why it matters

Without the concept of an inorder successor, it would be hard to move through a BST in sorted order efficiently. This would make operations like finding the next bigger element or deleting nodes more complex and slower. In real life, this means slower search and update operations in databases, file systems, or any software using BSTs.

Where it fits

Before learning this, you should understand what a Binary Search Tree is and how inorder traversal works. After this, you can learn about deletion in BSTs, balanced BSTs like AVL or Red-Black trees, and other tree traversal techniques.

Mental Model

Core Idea

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

Think of it like...

Imagine a line of people sorted by height. The inorder successor of a person is the very next taller person standing right after them in the line.

       20
      /  \
    10    30
      \     \
      15    40

Inorder traversal: 10 -> 15 -> 20 -> 30 -> 40
Successor of 15 is 20
Successor of 20 is 30

Build-Up - 7 Steps

1

Foundation

Understanding BST Structure

Concept: Learn the basic properties of a Binary Search Tree and how nodes are arranged.

A BST is a tree where each node has a value. For any node, all values in its left subtree are smaller, and all values in its right subtree are larger. This property helps in searching efficiently. Example: Node 20 has left child 10 and right child 30. 10 < 20 < 30 This ordering is true for every node in the tree.

Result

You can quickly decide which subtree to search based on the value you want.

Understanding the BST property is key because the inorder successor depends on this sorted order.

2

Foundation

Inorder Traversal Basics

Concept: Learn how inorder traversal visits nodes in ascending order in a BST.

Inorder traversal means: 1. Visit left subtree 2. Visit current node 3. Visit right subtree For the BST: 20 / \ 10 30 \ \ 15 40 The inorder traversal visits nodes in this order: 10, 15, 20, 30, 40.

Result

Inorder traversal of a BST produces sorted node values.

Knowing inorder traversal order helps identify what the 'next' node means in the BST.

3

Intermediate

Finding Successor When Right Child Exists

🤔Before reading on: If a node has a right child, do you think its successor is the right child itself or somewhere else? Commit to your answer.

Concept: If a node has a right child, its inorder successor is the smallest node in that right subtree.

For example, consider node 20 with right child 30: - The successor of 20 is the leftmost node in 20's right subtree. - If 30 has a left child, go left until no more left child. - If no left child, the right child itself is the successor. In the example tree, successor of 20 is 30 because 30 has no left child.

Result

You find the successor by going right once, then all the way left.

This step shows how the BST property guides us to find the next bigger node efficiently.

4

Intermediate

Finding Successor Without Right Child

🤔Before reading on: If a node has no right child, do you think its successor is above it or below it in the tree? Commit to your answer.

Concept: If a node has no right child, its successor is the nearest ancestor for which this node is in the left subtree.

For example, node 15 has no right child. - Move up to parent 10, then to 20. - 15 is in the right subtree of 10, so keep moving up. - 10 is in the left subtree of 20, so 20 is the successor of 15. This means we move up until we find a node that is a left child of its parent; that parent is the successor.

Result

You find the successor by moving up the tree until you find a node that is a left child of its parent.

Understanding tree structure and parent links is crucial to find successors without right children.

5

Intermediate

Implementing Successor Function in C

🤔Before reading on: Do you think the function needs parent pointers or can it work without them? Commit to your answer.

Concept: Implement the logic to find inorder successor using node pointers and possibly parent pointers.

Assuming each node has a pointer to its parent: 1. If node has right child, go right once, then left as far as possible. 2. Else, move up using parent pointers until you find a node that is left child of its parent. Code snippet: struct Node { int val; struct Node *left, *right, *parent; }; struct Node* inorderSuccessor(struct Node* node) { if (node->right) { node = node->right; while (node->left) node = node->left; return node; } struct Node* p = node->parent; while (p && node == p->right) { node = p; p = p->parent; } return p; }

Result

The function returns the correct inorder successor node or NULL if none exists.

Knowing how to use parent pointers simplifies the search for successors without right children.

6

Advanced

Successor Without Parent Pointers

🤔Before reading on: Can you find the successor without parent pointers by searching from the root? Commit to your answer.

Concept: If parent pointers are not available, find the successor by searching from the root node.

Algorithm: - Start from root. - If node's value is less than root's value, root could be successor; go left. - Else go right. - Keep track of the last node that could be successor. Code snippet: struct Node* inorderSuccessorWithoutParent(struct Node* root, struct Node* node) { struct Node* succ = NULL; while (root) { if (node->val < root->val) { succ = root; root = root->left; } else if (node->val > root->val) { root = root->right; } else { break; } } if (node->right) { struct Node* temp = node->right; while (temp->left) temp = temp->left; return temp; } return succ; }

Result

The function finds the inorder successor without needing parent pointers.

Searching from the root leverages BST properties to find successors even without parent links.

7

Expert

Handling Edge Cases and Performance

🤔Before reading on: Do you think the successor function always runs in O(log n) time? Commit to your answer.

Concept: Understand edge cases like no successor and analyze time complexity in balanced and unbalanced BSTs.

Edge cases: - Node is the maximum element (no successor, return NULL). - Node is NULL (return NULL). Performance: - In balanced BST, time is O(log n) because we move down or up the tree height. - In worst case (skewed tree), time can be O(n). Optimizations: - Use parent pointers to avoid searching from root. - Keep BST balanced to ensure efficient successor queries.

Result

You can handle all cases correctly and understand performance trade-offs.

Knowing edge cases and complexity helps write robust and efficient BST successor functions.

Under the Hood

The inorder successor works by exploiting the BST's sorted structure. If a node has a right subtree, the successor is the smallest node there, found by going left as far as possible. If no right subtree, the successor is an ancestor node where the current node lies in its left subtree, found by moving up parent links or searching from root. This relies on BST properties and tree traversal order.

Why designed this way?

This design leverages the BST's sorted nature to find the next bigger element efficiently without scanning the entire tree. Alternatives like linear search would be slower. Parent pointers simplify upward traversal but are optional, trading space for speed. The approach balances time and space complexity for common tree operations.

          ┌─────────────┐
          │   Start     │
          └──────┬──────┘
                 │
         Does node have right child?
                 │
        ┌────────┴────────┐
        │                 │
       Yes               No
        │                 │
Go right once, then    Move up to parent
keep going left       until node is left child
until no left child   of its parent
        │                 │
        └────────┬────────┘
                 │
          This node is successor
                 │
               End

Myth Busters - 3 Common Misconceptions

Quick: Is the inorder successor always the right child of the node? Commit yes or no.

Common Belief: Many think the inorder successor is always the right child of the node.

Reality: The successor is the leftmost node in the right subtree if it exists; otherwise, it is an ancestor node higher up the tree.

Why it matters: Assuming the successor is always the right child leads to wrong results and bugs when the node has no right child.

Quick: Can you find the inorder successor without parent pointers by only looking at the node? Commit yes or no.

Common Belief: Some believe you can find the successor by only looking at the node itself without any other information.

Reality: Without parent pointers or access to the root, you cannot find the successor if the node has no right child.

Why it matters: This misconception causes confusion and incorrect implementations that fail in common cases.

Quick: Does the inorder successor always exist for every node? Commit yes or no.

Common Belief: People often think every node has an inorder successor.

Reality: The maximum node in the BST has no inorder successor; the function should return NULL in this case.

Why it matters: Ignoring this leads to null pointer errors or infinite loops in code.

Expert Zone

1

When parent pointers exist, successor queries become simpler and faster, but they increase memory usage and complexity of tree updates.

2

In balanced BSTs, successor queries are guaranteed O(log n), but in skewed trees, worst-case time is O(n), affecting performance.

3

Successor logic is foundational for complex operations like node deletion and tree balancing, making it a critical building block.

When NOT to use

If you need guaranteed fast successor queries in large datasets, consider balanced BSTs like AVL or Red-Black trees. For very large or dynamic data, B-Trees or skip lists might be better. Also, if parent pointers are not available and root access is costly, alternative data structures may be preferable.

Production Patterns

In real systems, inorder successor logic is used in database indexing, file system directory traversal, and memory management. Implementations often combine successor logic with balancing algorithms to maintain performance. Parent pointers are common in production for efficient upward traversal.

Connections

Tree Traversals

Builds-on

Understanding inorder traversal is essential to grasp what the successor means and how to find it.

Balanced Binary Search Trees (AVL, Red-Black Trees)

Builds-on

Balanced trees maintain height to ensure successor queries remain efficient, showing how successor logic integrates with advanced tree structures.

Sorted Linked Lists

Similar pattern

The inorder successor in BSTs is like the next node in a sorted linked list, connecting tree traversal to linear data structures.

Common Pitfalls

#1 Assuming the successor is always the right child.

Wrong approach:

if (node->right) return node->right;
else return NULL;

Correct approach:

if (node->right) {
struct Node* temp = node->right;
while (temp->left) temp = temp->left;
return temp;
} else {
// move up to find successor
}

Root cause:

Misunderstanding that the successor is the smallest node in the right subtree, not just the immediate right child.

#2 Trying to find successor without parent pointers or root access when node has no right child.

Wrong approach:

return NULL; // assuming no successor if no right child and no parent pointer

Correct approach:

Search from root to find successor by comparing values and tracking potential successor nodes.

Root cause:

Not realizing that upward traversal requires parent pointers or root-based search.

#3 Not handling the case when node is the maximum element.

Wrong approach:

struct Node* succ = inorderSuccessor(node);
printf("%d", succ->val); // crashes if succ is NULL

Correct approach:

struct Node* succ = inorderSuccessor(node);
if (succ) printf("%d", succ->val);
else printf("No successor");

Root cause:

Ignoring that the maximum node has no successor and failing to check for NULL.

Key Takeaways

The inorder successor of a node in a BST is the next node visited in inorder traversal, representing the next bigger value.

If the node has a right child, the successor is the leftmost node in the right subtree; otherwise, it is the nearest ancestor where the node lies in the left subtree.

Parent pointers simplify finding successors without right children, but if unavailable, searching from the root using BST properties works.

Edge cases like the maximum node having no successor must be handled to avoid errors.

Understanding inorder successor logic is fundamental for efficient BST operations like deletion and traversal.

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