Inorder Successor in BST - Practice Coding Problems

Inorder Successor in BST - Problem

Given the root of a binary search tree and a node p in it, return the in-order successor of that node in the BST.

If the given node has no in-order successor in the tree, return null.

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

Input & Output

Example 1 — Node with Right Subtree

$ Input: root = [2,1,3], p = 1

› Output: 2

💡 Note: Node 1 has no right child, so we look for the ancestor where 1 is in the left subtree. Starting from root 2, since 1 < 2, node 2 is the successor of 1.

Example 2 — Node without Right Subtree

$ Input: root = [5,3,6,2,4,null,null,1], p = 6

› Output: null

💡 Note: Node 6 has no right child and is the largest node in the BST, so it has no inorder successor. Return null.

Example 3 — Leftmost in Right Subtree

$ Input: root = [5,3,6,2,4], p = 3

› Output: 4

💡 Note: Node 3 has a right child. The successor is the leftmost node in the right subtree of 3, which is node 4.

Constraints

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

Visualization

Tap to expand

Understanding the Visualization

Input

BST and target node p

Process

Use BST properties to find successor

Output

Next node in inorder sequence

Key Takeaway

🎯 Key Insight: BST structure allows us to find successors in O(h) time by following specific paths rather than visiting all nodes

Asked in

a Amazon 15 f Facebook 12 M Microsoft 10 G Google 8

The key insight is using BST properties to find successors efficiently. If the node has a right child, the successor is the leftmost node in the right subtree. Otherwise, it's the lowest ancestor where the node is in the left subtree. Best approach is BST optimization with Time: O(h), Space: O(1).

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force Inorder Traversal	O(n)	O(n)	Perform complete inorder traversal and find the next node after p
BST Property Optimization	O(h)	O(1)	Use BST properties to find successor without complete traversal

Brute Force Inorder Traversal — Algorithm Steps

Step 1: Perform complete inorder traversal and store all nodes
Step 2: Find node p in the sequence
Step 3: Return the next node if it exists, otherwise null

Visualization

Tap to expand

Step-by-Step Walkthrough

Traverse

Visit all nodes in inorder: left-root-right

Store

Build complete sequence of nodes

Find

Locate p and return next node

Code -

solution.c — C

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

struct TreeNode {
    int val;
    struct TreeNode* left;
    struct TreeNode* right;
};

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

void inorder(struct TreeNode* node, struct TreeNode** result, int* size) {
    if (!node) return;
    inorder(node->left, result, size);
    result[(*size)++] = node;
    inorder(node->right, result, size);
}

struct TreeNode* solution(struct TreeNode* root, struct TreeNode* p) {
    struct TreeNode* nodes[1000];
    int size = 0;
    inorder(root, nodes, &size);
    
    for (int i = 0; i < size; i++) {
        if (nodes[i]->val == p->val) {
            if (i + 1 < size) {
                return nodes[i + 1];
            }
            break;
        }
    }
    return NULL;
}

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

int main() {
    // Simplified parsing for basic test case
    struct TreeNode* root = createNode(2);
    root->left = createNode(1);
    root->right = createNode(3);
    
    int pVal = 1;
    struct TreeNode* pNode = findNode(root, pVal);
    struct TreeNode* result = solution(root, pNode);
    
    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 sequence

✓ Linear Growth

Space Complexity

O(n)

Stores all n nodes in traversal list plus recursion stack

⚡ Linearithmic Space

28.0K Views

Medium Frequency

~15 min Avg. Time

892 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

Brute Force Inorder Traversal — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler