In-order Successor of Binary Search Tree
Explore how to determine the in-order successor of a given node in a binary search tree. This lesson helps you understand the logic behind in-order traversal and learn an efficient method to locate the next node in sequence. You will gain the ability to implement the solution with optimal time and space complexity while handling edge cases effectively.
We'll cover the following...
Statement
Write a method to find the in-order successor of a BST node with a given value. 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
Consider the following BST:
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
Expected output
75
Try it yourself
Note: The binary tree node’s class has members
leftandright...