ProgramGuru

Find the Inorder Successor in a Binary Search Tree

Problem and examples

Given a binary search tree (BST) and a node p in it, find the inorder successor of that node. The inorder successor of a node is the node with the smallest key greater than p.val.

Note: It is guaranteed that the given node p exists in the tree. However, the successor might or might not exist.

Input Tree Target Node (p) Inorder Successor Description
[20, 10, 30, 5, 15, 25, 35] 15 20 Inorder successor of 15 is 20, the lowest ancestor for which 15 is in left subtree.
[20, 10, 30, 5, 15, 25, 35] 10 15 Successor is leftmost node in 10's right subtree: 15.
[20, 10, 30, 5, 15, 25, 35] 30 35 30 has a right child, and its leftmost node is 35 — the inorder successor.
[20, 10, 30, 5, 15, 25, 35] 35 null 35 is the rightmost node; it has no inorder successor.
[20, 10, null, 5, 15] 5 10 5 has no right child. Successor is the lowest ancestor for which 5 lies in the left subtree — 10.
[8, 3, 10, 1, 6, null, 14, null, null, 4, 7, 13] 6 7 6 has right child 7 → it's the inorder successor.

How it works

Understanding the Problem

We are given a Binary Search Tree (BST) and a node p. Our goal is to find the inorder successor of this node. An inorder successor is the node that comes immediately after p in the inorder traversal of the tree.

In an inorder traversal of a BST, we visit nodes in ascending order: left subtree → current node → right subtree. So, the inorder successor of a node p is the node with the smallest key greater than p.val.

Step-by-Step Solution with Example

step 1: Identify if node p has a right child

If p has a right child, then its inorder successor will be the leftmost node in the right subtree. This is because we go right once, and then as left as possible to find the next smallest value.

Example: Consider a BST: [4, 2, 6, null, 3, 5, 7]. If p = 4, since 4 has a right child (6), we go to 6, and then go left to find 5. So, the inorder successor is 5.

step 2: Handle the case when node p has no right child

If p does not have a right child, then we have to look at its ancestors. Specifically, we look for the lowest ancestor for which p is in its left subtree. This ancestor will be the next node in the inorder traversal.

We start from the root and simulate the traversal path to p. During this path, if we ever move left, we store the current node as a potential successor. If we move right, we do not update the successor.

Example: For the same BST, if p = 5, it has no right child. Starting from root (4), we move right to 6, then left to 5. Since we moved left from 6 to 5, 6 becomes the successor.

step 3: Account for edge case where p is the largest node

If p is the largest node in the tree, it will not have a successor. There is no node with a value greater than p, so the result should be null.

Example: If p = 7 in the same BST, 7 is the largest. There is no node after 7 in inorder traversal, so the answer is null.

step 4: Traverse and return the stored successor

We either return the leftmost node in the right subtree (step 1), or the stored ancestor (step 2). If neither exists, we return null.

Edge Cases

Tree is empty

If the BST is empty, there are no nodes to process. Return null.

Node p is null

If the input node is null, there’s no way to find a successor. Return null.

Tree has only one node

If the tree contains just one node and that node is p, there is no successor to find. Return null.

Node p is not present in the tree

This depends on the implementation — either you check if p exists in the tree or you assume it does. If it doesn’t exist, the answer should be null or an error should be raised depending on requirements.

Finally

Finding the inorder successor in a BST is an important operation and relies on understanding tree traversal and BST properties. By breaking the problem into two main scenarios (right child exists vs. no right child), and walking through intuitive examples, we can confidently solve this problem. Always remember to include boundary conditions like null nodes or the largest element to make your solution robust.

  1. Given a binary search tree (BST) and a target node p.
  2. If p.right exists, the inorder successor is the leftmost node in the right subtree.
  3. If p.right does not exist, initialize successor = null and traverse the tree starting from the root:
  4. While traversing, if p.val < current.val, update successor to the current node and move to current.left; otherwise, move to current.right.
  5. After the traversal, the recorded successor is the inorder successor of p.

Implementation and efficiency

C implementation

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

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

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

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

int main() {
    TreeNode* root = createNode(5);
    root->left = createNode(3);
    root->right = createNode(7);
    root->left->left = createNode(2);
    root->left->right = createNode(4);
    root->right->right = createNode(8);
    TreeNode* p = root->left; // Node with value 3
    TreeNode* succ = inorderSuccessor(root, p);
    printf("%d\n", succ ? succ->val : -1);
    return 0;
}

C++ implementation

#include <iostream>
using namespace std;

struct TreeNode {
    int val;
    TreeNode *left, *right;
    TreeNode(int x): val(x), left(nullptr), right(nullptr) {}
};

TreeNode* inorderSuccessor(TreeNode* root, TreeNode* p) {
    if (p->right) {
        TreeNode* curr = p->right;
        while (curr->left) curr = curr->left;
        return curr;
    }
    TreeNode* successor = nullptr;
    while (root) {
        if (p->val < root->val) {
            successor = root;
            root = root->left;
        } else {
            root = root->right;
        }
    }
    return successor;
}

int main() {
    TreeNode* root = new TreeNode(5);
    root->left = new TreeNode(3);
    root->right = new TreeNode(7);
    root->left->left = new TreeNode(2);
    root->left->right = new TreeNode(4);
    root->right->right = new TreeNode(8);
    TreeNode* p = root->left; // Node with value 3
    TreeNode* succ = inorderSuccessor(root, p);
    cout << (succ ? succ->val : -1) << endl;
    return 0;
}

Python implementation

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def inorderSuccessor(root, p):
    if p.right:
        curr = p.right
        while curr.left:
            curr = curr.left
        return curr
    successor = None
    while root:
        if p.val < root.val:
            successor = root
            root = root.left
        else:
            root = root.right
    return successor

if __name__ == '__main__':
    root = TreeNode(5,
            TreeNode(3, TreeNode(2), TreeNode(4)),
            TreeNode(7, None, TreeNode(8)))
    p = root.left  # Node with value 3
    successor = inorderSuccessor(root, p)
    print(successor.val if successor else None)

Java implementation

class TreeNode {
    int val;
    TreeNode left, right;
    TreeNode(int x) { val = x; }
}

public class InorderSuccessorBST {
    public TreeNode inorderSuccessor(TreeNode root, TreeNode p) {
        if (p.right != null) {
            TreeNode curr = p.right;
            while (curr.left != null) {
                curr = curr.left;
            }
            return curr;
        }
        TreeNode successor = null;
        while (root != null) {
            if (p.val < root.val) {
                successor = root;
                root = root.left;
            } else {
                root = root.right;
            }
        }
        return successor;
    }

    public static void main(String[] args) {
        TreeNode root = new TreeNode(5);
        root.left = new TreeNode(3);
        root.right = new TreeNode(7);
        root.left.left = new TreeNode(2);
        root.left.right = new TreeNode(4);
        root.right.right = new TreeNode(8);
        InorderSuccessorBST sol = new InorderSuccessorBST();
        TreeNode p = root.left; // Node with value 3
        TreeNode successor = sol.inorderSuccessor(root, p);
        System.out.println(successor != null ? successor.val : "null");
    }
}

JavaScript implementation

class TreeNode {
    constructor(val, left = null, right = null) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

function inorderSuccessor(root, p) {
    if (p.right) {
        let curr = p.right;
        while (curr.left) curr = curr.left;
        return curr;
    }
    let successor = null;
    while (root) {
        if (p.val < root.val) {
            successor = root;
            root = root.left;
        } else {
            root = root.right;
        }
    }
    return successor;
}

const root = new TreeNode(5,
            new TreeNode(3, new TreeNode(2), new TreeNode(4)),
            new TreeNode(7, null, new TreeNode(8)));
const p = root.left;
const successor = inorderSuccessor(root, p);
console.log(successor ? successor.val : null);

Go implementation

package main

import (
    "fmt"
)

type TreeNode struct {
    Val   int
    Left  *TreeNode
    Right *TreeNode
}

func inorderSuccessor(root, p *TreeNode) *TreeNode {
    if p.Right != nil {
        curr := p.Right
        for curr.Left != nil {
            curr = curr.Left
        }
        return curr
    }
    var successor *TreeNode
    for root != nil {
        if p.Val < root.Val {
            successor = root
            root = root.Left
        } else {
            root = root.Right
        }
    }
    return successor
}

func main() {
    root := &TreeNode{5,
        &TreeNode{3, &TreeNode{2, nil, nil}, &TreeNode{4, nil, nil}},
        &TreeNode{7, nil, &TreeNode{8, nil, nil}}}
    p := root.Left
    succ := inorderSuccessor(root, p)
    if succ != nil {
        fmt.Println(succ.Val)
    } else {
        fmt.Println("null")
    }
}

Rust implementation

struct TreeNode {
    val: i32,
    left: Option<Box<TreeNode>>,
    right: Option<Box<TreeNode>>,
}

fn inorder_successor(mut root: Option<&Box<TreeNode>>, p_val: i32) -> Option<i32> {
    let mut successor = None;
    while let Some(node) = root {
        if p_val < node.val {
            successor = Some(node.val);
            root = node.left.as_ref();
        } else {
            root = node.right.as_ref();
        }
    }
    successor
}

fn main() {
    let root = Box::new(TreeNode {
        val: 5,
        left: Some(Box::new(TreeNode {
            val: 3,
            left: Some(Box::new(TreeNode { val: 2, left: None, right: None })),
            right: Some(Box::new(TreeNode { val: 4, left: None, right: None }))
        })),
        right: Some(Box::new(TreeNode {
            val: 7,
            left: None,
            right: Some(Box::new(TreeNode { val: 8, left: None, right: None }))
        })),
    });
    let result = inorder_successor(Some(&root), 3);
    println!("{}", result.unwrap_or(-1));
}

Kotlin implementation

class TreeNode(var val_: Int) {
    var left: TreeNode? = null
    var right: TreeNode? = null
}

fun inorderSuccessor(root: TreeNode?, p: TreeNode): TreeNode? {
    if (p.right != null) {
        var curr = p.right
        while (curr?.left != null) {
            curr = curr.left
        }
        return curr
    }
    var curr = root
    var successor: TreeNode? = null
    while (curr != null) {
        if (p.val_ < curr.val_) {
            successor = curr
            curr = curr.left
        } else {
            curr = curr.right
        }
    }
    return successor
}

fun main() {
    val root = TreeNode(5)
    root.left = TreeNode(3)
    root.right = TreeNode(7)
    root.left?.left = TreeNode(2)
    root.left?.right = TreeNode(4)
    root.right?.right = TreeNode(8)
    val p = root.left!!
    val succ = inorderSuccessor(root, p)
    println(succ?.val_ ?: "null")
}

Swift implementation

class TreeNode {
    var val: Int
    var left: TreeNode?
    var right: TreeNode?
    init(_ val: Int) {
        self.val = val
    }
}

func inorderSuccessor(_ root: TreeNode?, _ p: TreeNode) -> TreeNode? {
    if let right = p.right {
        var curr = right
        while let next = curr.left {
            curr = next
        }
        return curr
    }
    var curr = root
    var successor: TreeNode? = nil
    while let node = curr {
        if p.val < node.val {
            successor = node
            curr = node.left
        } else {
            curr = node.right
        }
    }
    return successor
}

let root = TreeNode(5)
root.left = TreeNode(3)
root.right = TreeNode(7)
root.left?.left = TreeNode(2)
root.left?.right = TreeNode(4)
root.right?.right = TreeNode(8)
let p = root.left!
if let succ = inorderSuccessor(root, p) {
    print(succ.val)
} else {
    print("null")
}

TypeScript implementation

class TreeNode {
    val: number;
    left: TreeNode | null;
    right: TreeNode | null;
    constructor(val: number, left: TreeNode | null = null, right: TreeNode | null = null) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

function inorderSuccessor(root: TreeNode | null, p: TreeNode): TreeNode | null {
    if (p.right) {
        let curr = p.right;
        while (curr.left) curr = curr.left;
        return curr;
    }
    let successor: TreeNode | null = null;
    while (root) {
        if (p.val < root.val) {
            successor = root;
            root = root.left;
        } else {
            root = root.right;
        }
    }
    return successor;
}

const root = new TreeNode(5,
    new TreeNode(3, new TreeNode(2), new TreeNode(4)),
    new TreeNode(7, null, new TreeNode(8)));
const p = root.left!;
const successor = inorderSuccessor(root, p);
console.log(successor ? successor.val : null);