DSA problem
Inorder Successor in BST II
You are given a node node in a binary search tree. Every node in this tree carries an additional parent pointer in addition to the usual left and right children. Return the in-order successor of node without access to the root of the tree.
The catch is that you cannot start a fresh walk from the root because you do not have it. You only have the local view through node.left, node.right, and node.parent. You must derive the successor purely from these references.
There are exactly two cases. Case 1: node has a non-null right child. Then by the BST property, the successor is the leftmost descendant of that right child — keep stepping into .left until you cannot anymore. Case 2: node has no right child. Then the successor lies somewhere up the parent chain. Walk parents until you arrive at a parent for which the previous node was its left child; that parent is the successor. If you walk off the top (parent becomes null), there is no successor and you return null.
This algorithm runs in O(h) time and O(1) space — only two pointers are used. It works on arbitrary BSTs with parent pointers and never needs the root.
Examples
tree = [2,1,3], node = 12tree = [5,3,6,2,4,null,null,1], node = 6nulltree = [5,3,6,2,4,null,null,1], node = 45Constraints
- The number of nodes in the tree is in the range [1, 10^4].
- -10^5 <= Node.val <= 10^5
- All Nodes will have unique values.
- You will only have access to a node, not the root.
3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.