Inorder Successor in BST II - Practice Coding Problems

Inorder Successor in BST II - Problem

Given a node in a binary search tree, return the in-order successor of that node in the BST. If that node has no in-order successor, return null.

The successor of a node is the node with the smallest key greater than node.val.

You will have direct access to the node but not to the root of the tree. Each node will have a reference to its parent node.

The definition for Node is:

class Node {
    public int val;
    public Node left;
    public Node right;
    public Node parent;
}

Input & Output

Example 1 — Node with Right Subtree

$ Input: node = Node(3) in BST [2,3,4,5,6,7,8]

› Output: Node(5)

💡 Note: Node 3 has a right subtree starting with 5. The leftmost node in this right subtree is 5, so the successor is 5.

Example 2 — Node without Right Subtree

$ Input: node = Node(4) in BST [2,3,4,5,6,7,8]

› Output: Node(5)

💡 Note: Node 4 has no right subtree. We go up to parent 3, then to parent 5. Since 4→3→5 and we came from the left at 5, the successor is 5.

Example 3 — Rightmost Node

$ Input: node = Node(8) in BST [2,3,4,5,6,7,8]

› Output: null

💡 Note: Node 8 is the rightmost node in the BST, so it has no inorder successor. Return null.

Constraints

The number of nodes in the tree is in the range [1, 10⁴]
-10⁵ ≤ Node.val ≤ 10⁵
All Node.val are unique

Visualization

Tap to expand

Understanding the Visualization

Input

Given a node in BST with parent pointers

Process

Use BST properties to find successor efficiently

Output

Return the inorder successor or null

Key Takeaway

🎯 Key Insight: Use BST structure and parent pointers to find successor in O(h) time without full traversal

Asked in

G Google 25 f Facebook 20 M Microsoft 18 a Amazon 15

The key insight is to use BST properties with parent pointers. If the node has a right subtree, find the leftmost node there. Otherwise, traverse up until finding an ancestor where we came from the left. Best approach uses BST Property Utilization with Time: O(h), Space: O(1).

Common Approaches

Approach	Time	Space	Notes
✓ Complete Tree Traversal	O(n)	O(n)	Traverse entire tree to find all nodes, then locate successor
BST Property Utilization	O(h)	O(1)	Use BST structure to find successor without full traversal

Complete Tree Traversal — Algorithm Steps

Navigate to root using parent pointers
Perform inorder traversal to get sorted list
Find given node and return next element

Visualization

Tap to expand

Step-by-Step Walkthrough

Navigate to Root

Follow parent pointers to find root

Inorder Traversal

Visit all nodes in sorted order

Find Successor

Locate target node and return next element

Code -

solution.c — C

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

struct Node {
    int val;
    struct Node* left;
    struct Node* right;
    struct Node* parent;
};

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

void inorder(struct Node* root, struct Node** nodes, int* count) {
    if (root) {
        inorder(root->left, nodes, count);
        nodes[*count] = root;
        (*count)++;
        inorder(root->right, nodes, count);
    }
}

struct Node* solution(struct Node* node) {
    if (!node) return NULL;
    
    // Find root
    struct Node* root = node;
    while (root->parent) {
        root = root->parent;
    }
    
    // Inorder traversal
    struct Node* nodes[1000];
    int count = 0;
    inorder(root, nodes, &count);
    
    // Find successor
    for (int i = 0; i < count; i++) {
        if (nodes[i] == node && i + 1 < count) {
            return nodes[i + 1];
        }
    }
    return NULL;
}

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

int main() {
    int nodeVal;
    scanf("%d", &nodeVal);
    
    // Create sample BST
    struct Node* root = createNode(5);
    root->left = createNode(3);
    root->left->parent = root;
    root->right = createNode(7);
    root->right->parent = root;
    root->left->left = createNode(2);
    root->left->left->parent = root->left;
    root->left->right = createNode(4);
    root->left->right->parent = root->left;
    root->right->left = createNode(6);
    root->right->left->parent = root->right;
    root->right->right = createNode(8);
    root->right->right->parent = root->right;
    
    struct Node* targetNode = findNode(root, nodeVal);
    struct Node* result = solution(targetNode);
    if (result) {
        printf("%d\n", result->val);
    } else {
        printf("null\n");
    }
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

Must visit all n nodes to build complete inorder list

✓ Linear Growth

Space Complexity

O(n)

Stores all n nodes in list plus recursion stack

⚡ Linearithmic Space

98.2K Views

Medium Frequency

~15 min Avg. Time

1.8K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Complete Tree Traversal — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler