Understanding the Problem
We are given a Binary Search Tree (BST) and a node p
. Our goal is to find the inorder successor of this node. An inorder successor is the node that comes immediately after p
in the inorder traversal of the tree.
In an inorder traversal of a BST, we visit nodes in ascending order: left subtree → current node → right subtree. So, the inorder successor of a node p
is the node with the smallest key greater than p.val
.
Step-by-Step Solution with Example
step 1: Identify if node p
has a right child
If p
has a right child, then its inorder successor will be the leftmost node in the right subtree. This is because we go right once, and then as left as possible to find the next smallest value.
Example: Consider a BST: [4, 2, 6, null, 3, 5, 7]
. If p = 4
, since 4 has a right child (6), we go to 6, and then go left to find 5. So, the inorder successor is 5.
step 2: Handle the case when node p
has no right child
If p
does not have a right child, then we have to look at its ancestors. Specifically, we look for the lowest ancestor for which p
is in its left subtree. This ancestor will be the next node in the inorder traversal.
We start from the root and simulate the traversal path to p
. During this path, if we ever move left, we store the current node as a potential successor. If we move right, we do not update the successor.
Example: For the same BST, if p = 5
, it has no right child. Starting from root (4), we move right to 6, then left to 5. Since we moved left from 6 to 5, 6 becomes the successor.
step 3: Account for edge case where p
is the largest node
If p
is the largest node in the tree, it will not have a successor. There is no node with a value greater than p
, so the result should be null
.
Example: If p = 7
in the same BST, 7 is the largest. There is no node after 7 in inorder traversal, so the answer is null.
step 4: Traverse and return the stored successor
We either return the leftmost node in the right subtree (step 1), or the stored ancestor (step 2). If neither exists, we return null
.
Edge Cases
Tree is empty
If the BST is empty, there are no nodes to process. Return null
.
Node p
is null
If the input node is null
, there’s no way to find a successor. Return null
.
Tree has only one node
If the tree contains just one node and that node is p
, there is no successor to find. Return null
.
Node p
is not present in the tree
This depends on the implementation — either you check if p
exists in the tree or you assume it does. If it doesn’t exist, the answer should be null
or an error should be raised depending on requirements.
Finally
Finding the inorder successor in a BST is an important operation and relies on understanding tree traversal and BST properties. By breaking the problem into two main scenarios (right child exists vs. no right child), and walking through intuitive examples, we can confidently solve this problem. Always remember to include boundary conditions like null nodes or the largest element to make your solution robust.
Comments
Loading comments...