In-order Successor Binary Search Tree With Parent Pointers
Explore how to identify the in-order successor of a node in a binary search tree with parent pointers. This lesson guides you through locating nodes, handling right-child scenarios, and traversing parent links to find successors. Understand the solution's time and space complexities while practicing a key tree traversal technique vital for coding interviews.
We'll cover the following...
Statement
Write a method to find the in-order successor of a given BST node using parent pointers. Return -1 if the node with the given value does not exist.
The in-order successor of a node in a BST is the node with the smallest key greater than the key of the current node. This is the same as the next node in an in-order traversal of the BST.
Example
In the following BST, each node has a parent pointer.
In the table below, we can see the in-order successor for some of the nodes in this tree:
| Node | In-Order Successor |
|---|---|
| 25 | 50 |
| 100 | 125 |
| 350 | NULL |
Note: The in-order successor of 350 is NULL since that’s the last node.
Sample input
The input list below represents the level-order traversal of the binary search tree, while the value that follows represents the node whose in-order successor we need to find:
[100, 50, 200, 25, 75, 125, 350], 50