Is Inorder Successor in BST easy or hard?

The problem is generally classified as Medium difficulty. Understanding inorder traversal is straightforward, but recognizing how to exploit BST ordering to achieve an O(h) solution is the key interview insight.

How to solve Inorder Successor in BST in O(h)?

Start from the root and compare p.val with the current node. If p.val is smaller, store the current node as a potential successor and move left. If p.val is greater or equal, move right. Continue until reaching null, and the stored candidate will be the inorder successor.

Inorder Successor in BST Python or Java solution

Most implementations follow the same BST search pattern in Python, Java, C++, or other languages. Maintain a variable for the successor while traversing from the root and update it whenever you encounter a node with value greater than p.val before moving left.

What is the best approach for Inorder Successor in BST?

The best approach uses the Binary Search Tree property to perform a guided search. Traverse from the root while tracking a candidate successor whenever the current node value is greater than p.val. This runs in O(h) time where h is the height of the tree and uses O(1) extra space.

What data structure is used in Inorder Successor in BST?

The problem is based on the Binary Search Tree data structure. Solutions typically combine BST ordering with traversal techniques such as Depth-First Search or binary search-style navigation through the tree.

What is the time complexity of Inorder Successor in BST?

The optimal solution runs in O(h) time where h is the height of the Binary Search Tree. In balanced trees this becomes O(log n), while in the worst case of a skewed tree it can degrade to O(n). Space complexity is O(1) because no additional data structures are required.

Is Inorder Successor in BST asked at Google Amazon or Meta?

Inorder successor problems frequently appear in interviews at companies like Amazon, Google, and Meta because they test understanding of Binary Search Trees and traversal logic. Variants may ask for successor with parent pointers or require handling multiple queries efficiently.

Description Solution Video 12:09

285. Inorder Successor in BST

Medium51.2% acceptance6 companiesPremium elsewhere, free here

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.

Example 1:

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

Example 2:

Input: root = [5,3,6,2,4,null,null,1], p = 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, 10⁴].
-10⁵ <= Node.val <= 10⁵
All Nodes will have unique values.

Asked at 6 companies

Pocket Gems DocuSign Microsoft Meta

Google Amazon

Topics

12:09

Still stuck?Read the written solution, or watch a walkthrough.

Open solution

285. Inorder Successor in BST

Asked at 6 companies

Topics

Similar problems