Skip to main content
Talentd

Inorder Successor in BST II - Solution & Explanation

MediumPremiumFree on FleetCodeTreeBinary Search TreeBinary Tree8 min readAsked at: Meta, Google, Arista Networks
Practice this problem

Problem Statement

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. Below is the definition for Node:

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

 

Example 1:

Input: tree = [2,1,3], node = 1
Output: 2
Explanation: 1's in-order successor node is 2. Note that both the node and the return value is of Node type.

Example 2:

Input: tree = [5,3,6,2,4,null,null,1], node = 6
Output: null
Explanation: There is no in-order successor of the current node, so the answer is null.

 

Constraints:

  • The number of nodes in the tree is in the range [1, 104].
  • -105 <= Node.val <= 105
  • All Nodes will have unique values.

 

Follow up: Could you solve it without looking up any of the node's values?

Approach Overview

Problem Overview: Given a node in a Binary Search Tree where each node also stores a parent pointer, return its inorder successor. The successor is the next node visited during an inorder traversal (left → root → right). If no such node exists, return null.

Approach 1: Full Inorder Traversal (O(n) time, O(n) space)

The straightforward solution performs a complete inorder traversal of the binary tree and stores the visited nodes in an array. Once traversal finishes, iterate through the array to locate the given node and return the next element. This works because inorder traversal of a binary search tree produces nodes in sorted order. The downside is unnecessary work: the algorithm visits every node even though the successor might be nearby.

Approach 2: Case Analysis Using Parent Pointers (O(h) time, O(1) space)

The structure provides a parent pointer, which allows upward traversal without needing the root. Two structural cases determine the successor. First, if the node has a right child, the successor is the leftmost node in the right subtree. Move to node.right, then repeatedly follow left pointers until no more exist.

If the node does not have a right child, move upward through parent pointers. Continue climbing while the current node is the right child of its parent. The first time you encounter a node that is the left child of its parent, that parent is the inorder successor. If you reach the top without finding such a relationship, the given node is the largest element and has no successor.

This approach relies on BST ordering properties and avoids scanning unrelated parts of the tree. The traversal depth never exceeds the tree height h, which keeps runtime efficient. Space usage stays constant because only pointer references are used.

Recommended for interviews: The parent-pointer case analysis is the expected solution. It demonstrates understanding of tree traversal properties and BST ordering while keeping complexity at O(h) time and O(1) space. Mentioning the full inorder traversal first shows baseline reasoning, but interviewers typically look for the optimized parent traversal.

Solution

If the node has a right subtree, then the in-order successor of node is the leftmost node in the right subtree.

If the node does not have a right subtree, then if node is the right child of its parent, we continue to search upwards until the parent of the node is null, or the node is the left child of its parent. In this case, the parent node is the in-order successor.

The time complexity is O(h), where h is the height of the binary tree. The space complexity is O(1).

Code

PythonJavaC++GoTypeScriptJavaScript

Python

Java

C++

Go

TypeScript

JavaScript

Try this approach in the editor →

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Full Inorder TraversalO(n)O(n)Simple baseline solution when you want a straightforward traversal without relying on BST properties.
Parent Pointer Case AnalysisO(h)O(1)Optimal approach when nodes contain parent references; traverses only the relevant subtree or ancestor chain.

Video Solution

Leetcode 510. Inorder Successor in BST II | Logic Coding • Xian Zhang • 1,113 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Inorder Successor in BST II easy or hard?
The problem is rated Medium because the logic requires recognizing two structural cases in a BST. Developers familiar with inorder traversal and tree relationships typically solve it quickly once they consider the right-subtree and parent-climb scenarios.
Inorder Successor in BST II Python/Java solution
Implement two checks: if node.right exists, move to the leftmost node of that subtree. Otherwise, keep moving to node.parent while the current node is the right child. The first parent where the node is a left child becomes the successor. This logic translates directly to Python, Java, C++, Go, and JavaScript.
How to solve Inorder Successor in BST II in O(n)?
An O(n) approach performs a full inorder traversal of the tree and stores nodes in a list. Because inorder traversal of a BST yields sorted order, the successor of the given node is simply the next element in that list. This method is easy to implement but uses O(n) time and O(n) space.
What is the best approach for Inorder Successor in BST II?
The optimal approach uses the parent pointer and BST structure. If the node has a right child, the successor is the leftmost node in the right subtree. Otherwise, move upward using parent pointers until the node becomes a left child of its parent. This runs in O(h) time and O(1) space where h is the tree height.
Is Inorder Successor in BST II asked at Google/Amazon/Meta?
BST traversal and successor/predecessor problems frequently appear in interviews at companies like Google, Amazon, and Meta. Variants include finding the successor with or without parent pointers and computing it given only the root. The problem tests understanding of BST ordering and tree navigation.
What data structure is used in Inorder Successor in BST II?
The problem uses a Binary Search Tree where each node also contains a parent pointer. The algorithm relies on BST ordering and pointer traversal across parent, left, and right references. No additional data structures are required for the optimal O(1) space solution.
What is the time complexity of Inorder Successor in BST II?
The optimal parent-pointer solution runs in O(h) time and O(1) space, where h is the height of the BST. In the worst case of a skewed tree, h can be O(n), but in balanced trees it is O(log n). A brute force inorder traversal takes O(n) time and O(n) extra space.

Ready to solve this problem?

Practice Inorder Successor in BST II with our built-in code editor and test cases.

Practice on FleetCode
Previous

Inorder Successor in BST