Inorder Successor in BST II solution and explanation
Google
9 more videos on this problem
Leetcode 510. Inorder Successor in BST II | Logic CodingXian Zhang · 7:02 · 1K views
LeetCode 510. Inorder Successor in BST II | Inorder Successor in BST Part 2 | TreeBase Case · 6:21 · 412 views
LeetCode. 510. Inorder Successor in BST II TechZoo PythonTechZoo · 6:01 · 353 views
LeetCode Q 510. Inorder Successor in BST IISweet AI · 7:04 · 127 views
LeetCode 510 | Inorder Successor in BST II | JavascriptKun's Dev · 7:38 · 118 views
ทำโจทย์ Leetcode: Inorder Successor in BST IITP Coder · 11:38 · 70 views
510. Inorder Successor in BST II [01/07/21 - 4/5]KG修罗场 · 8:10 · 50 views
Leetcode 510. Inorder Successor in BST II (tree traversal)LetsCode · 18:04 · 48 views
Inorder Successor In BST IIOwen Wu · 2:36 · 23 views
LeetCode 510: Inorder Successor in BST IIAlitaCode · 25:00 · 2 views
The 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. 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).
"""
# Definition for a Node.
class Node:
def __init__(self, val):
self.val = val
self.left = None
self.right = None
self.parent = None
"""
class Solution:
def inorderSuccessor(self, node: 'Node') -> 'Optional[Node]':
if node.right:
node = node.right
while node.left:
node = node.left
return node
while node.parent and node.parent.right is node:
node = node.parent
return node.parent/*
// Definition for a Node.
class Node {
public int val;
public Node left;
public Node right;
public Node parent;
};
*/
class Solution {
public Node inorderSuccessor(Node node) {
if (node.right != null) {
node = node.right;
while (node.left != null) {
node = node.left;
}
return node;
}
while (node.parent != null && node.parent.right == node) {
node = node.parent;
}
return node.parent;
}
}/*
// Definition for a Node.
class Node {
public:
int val;
Node* left;
Node* right;
Node* parent;
};
*/
class Solution {
public:
Node* inorderSuccessor(Node* node) {
if (node->right) {
node = node->right;
while (node->left) {
node = node->left;
}
return node;
}
while (node->parent && node->parent->right == node) {
node = node->parent;
}
return node->parent;
}
};/**
* // Definition for a Node.
* function Node(val) {
* this.val = val;
* this.left = null;
* this.right = null;
* this.parent = null;
* };
*/
/**
* @param {Node} node
* @return {Node}
*/
var inorderSuccessor = function (node) {
if (node.right) {
node = node.right;
while (node.left) {
node = node.left;
}
return node;
}
while (node.parent && node === node.parent.right) {
node = node.parent;
}
return node.parent;
};/**
* Definition for a binary tree node.
* class Node {
* val: number
* left: Node | null
* right: Node | null
* parent: Node | null
* constructor(val?: number, left?: Node | null, right?: Node | null, parent?: Node | null) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* this.parent = (parent===undefined ? null : parent)
* }
* }
*/
function inorderSuccessor(node: Node | null): Node | null {
if (node.right) {
node = node.right;
while (node.left) {
node = node.left;
}
return node;
}
while (node.parent && node === node.parent.right) {
node = node.parent;
}
return node.parent;
}/**
* Definition for Node.
* type Node struct {
* Val int
* Left *Node
* Right *Node
* Parent *Node
* }
*/
func inorderSuccessor(node *Node) *Node {
if node.Right != nil {
node = node.Right
for node.Left != nil {
node = node.Left
}
return node
}
for node.Parent != nil && node == node.Parent.Right {
node = node.Parent
}
return node.Parent
}Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Full Inorder Traversal | O(n) | O(n) | Simple baseline solution when you want a straightforward traversal without relying on BST properties. |
| Parent Pointer Case Analysis | O(h) | O(1) | Optimal approach when nodes contain parent references; traverses only the relevant subtree or ancestor chain. |
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.