285. Inorder Successor in BST
Problem Description
The problem is set within the context of a binary search tree (BST), a type of binary tree where each node has the following properties:
- The left subtree of a node contains only nodes with keys less than the node's key.
- The right subtree of a node contains only nodes with keys greater than the node's key.
- Both the left and right subtrees must also be binary search trees.
Given such a tree and a particular node p
in it, you need to find the "in-order successor" of that node. The in-order successor for a given node p
in a BST is defined as the node with the smallest key that is greater than p.val
. If such a node doesn't exist, in other words, if p
is the node with the highest value in the tree, the function should return null
.
The in-order traversal of a BST produces the node values in an ascending order. So the task could also be seen as finding the next node in the in-order traversal sequence.
Flowchart Walkthrough
Let's utilize the algorithm Flowchart to determine the most suitable approach for solving Leetcode 285: Inorder Successor in BST. Hereās how you can navigate through the diagram for this problem:
Is it a graph?
- No: Although technically a Binary Search Tree (BST) could be considered a type of graph, for algorithm purposes here, BSTs are typically addressed under tree-specific algorithms, not general graph theory.
Is it a tree?
- Yes: A BST is a type of binary tree which adheres to specific sorting properties.
Since the problem focuses on finding the inorder successor in a BST, we pursue the recommended algorithms for processing trees:
DFS (Depth-First Search) is suggested as an effective method for trees:
- Since the traversal or searching within a tree structure is the main goal here, and DFS is especially effective for tree traversals (inorder, preorder, postorder), it fits perfectly for finding the inorder successor. The depth-first nature of DFS allows us to deeply and sequentially traverse the BST, adhering naturally to the properties required to locate an inorder successor.
Conclusion: Following the flowchart, Depth-First Search (DFS) is indeed the appropriate algorithm to handle the task of finding an inorder successor in a Binary Search Tree, efficiently navigating the tree structure to find the desired result.
Intuition
When trying to understand the solution, it's critical to grasp what it means by in-order traversal and how the properties of a binary search tree can streamline our search for the successor node.
The in-order traversal for a BST involves visiting the left subtree, then the node itself, and then the right subtree. When looking for the successor of node p
, if p
has a right subtree, then the successor would be the leftmost node in that right subtree. If p
does not have a right subtree, the successor would be one of its ancestors, specifically the one for whom p
is situated in the left subtree.
The proposed solution uses this understanding and traverses the tree starting from the root. At each step, it compares the current node's value to p.val
to decide the direction of the search:
- If the current node's value is greater than
p.val
, the current node is a potential successor, and we go left to find a smaller one that is still larger thanp.val
. - If the current node's value is less than or equal to
p.val
, the current node can't be the successor, and we go right to find a larger one.
The variable ans
is used to keep track of the latest potential successor. This works because of the BST property: going left finds smaller keys and going right finds larger keys. When the algorithm finishes traversing the tree (root
becomes None
), the ans
variable either contains the in-order successor node or remains None
, meaning there is no successor (if p
is the maximum element).
This algorithm ensures that we only travel down the tree once, providing an efficient solution with O(h) time complexity, where h is the height of the tree.
Learn more about Tree, Depth-First Search, Binary Search Tree and Binary Tree patterns.
Solution Approach
The implementation of the solution follows a straightforward approach utilizing the binary search tree properties to efficiently find the in-order successor.
Firstly, let's outline the core components of the algorithm:
- While Loop: The algorithm uses a loop to iterate through the nodes of the tree, starting at the
root
. The loop continues untilroot
becomesNone
, which means we have reached the end of our search path in the BST. - Conditional Checking: Inside the loop, a conditional check compares the current node's value (
root.val
) with the value of the nodep
(p.val
). This comparison dictates the traversal direction because of the binary search tree arrangement. - Potential Successor Update (
ans
): If the current node's value is greater thanp.val
, it means this node could potentially be the successor. We store this node toans
and continue searching to the left for a smaller value that would still be larger thanp.val
. - Traversal Direction:
- If
root.val
>p.val
, we move left (root = root.left
) in search of a smaller yet greater value thanp.val
. - If
root.val
<=p.val
, we move right (root = root.right
) since we know that all values in the left subtree are smaller and cannot be the successor.
- If
The algorithm makes use of the BST property that left descendants are smaller and right descendants are larger than the node itself. Hence, we can discard half of the tree in each step of the while loop, similar to a binary search.
There is no need to keep track of already visited nodes because the potential successor (ans
) is updated only when moving left, ensuring that we always have the closest higher value to p.val
.
Additionally, no extra data structures are required, and the solution makes in-place updates without modifying the tree, hence the space complexity is O(1).
The algorithm terminates when we can no longer traverse the tree (when root
is None
), which means we can return the ans
value as the in-order successor. If no such successor exists (i.e., p
is the maximum value in the BST), the ans
remains None
, which the function returns as specified.
Here's a closer look at the code snippet which encapsulates the algorithm:
class Solution:
def inorderSuccessor(self, root: TreeNode, p: TreeNode) -> Optional[TreeNode]:
ans = None
while root:
if root.val > p.val:
ans = root
root = root.left
else:
root = root.right
return ans
The single pass through the tree and constant time operations on each node's value guarantee the solution is time-efficient, running in O(h) time where h is the height of the tree. This effectively means that in the worst case scenario (a skewed tree), where the tree shape resembles a linked list, the algorithm could take O(n) time where n is the number of nodes, since the tree's height would be equivalent to the number of nodes.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's illustrate the solution approach using a simple binary search tree and following the steps to find the in-order successor of a given node p
. Consider the following BST:
4 / \ 2 6 / \ / \ 1 3 5 7
Let's find the in-order successor of the node p
with a value of 3
.
- We start at the root of the tree, which is the node with the value
4
. - We compare
p.val
(which is3
) withroot.val
(which is4
).- Since
4
is greater than3
, the node with4
could be the in-order successor. We save this node and move to the left to look for an even closer value greater than3
.
- Since
- Now,
root
is at the node with the value2
. - We compare
p.val
with the newroot.val
(2
).- Since
2
is less than3
, we discard the left subtree including the current node and move right to find a larger value.
- Since
- However, the right child of
2
is the nodep
itself. So, we move to the right subtree ofp
. - Because
p
doesn't have a right subtree, our loop terminates, and we return the storedans
, which is4
.
In this example, the in-order successor of node p
with value 3
is the node with value 4
.
Here's a breakdown of how the code snippet implements this logic:
class Solution:
def inorderSuccessor(self, root: TreeNode, p: TreeNode) -> Optional[TreeNode]:
ans = None
while root:
if root.val > p.val:
ans = root # Potentially a successor, so we update `ans`.
root = root.left # Search for an even closer value on the left.
else:
root = root.right # Current or left values are not greater, we go right.
return ans
This walk-through demonstrates the algorithm's ability to leverage the BST properties to efficiently find the in-order successor with minimal time complexity.
Solution Implementation
1# Definition for a binary tree node.
2class TreeNode:
3 def __init__(self, value):
4 self.val = value
5 self.left = None
6 self.right = None
7
8
9class Solution:
10 def inorderSuccessor(self, root: TreeNode, p: TreeNode) -> TreeNode:
11 # Initialize variable to store the inorder successor
12 successor = None
13
14 # Traverse the tree starting with the root
15 while root:
16 # If current node's value is greater than 'p's value,
17 # tentative successor is found (potentially there could be a closer one).
18 if root.val > p.val:
19 successor = root
20 # Move to the left subtree to find the closest ancestor
21 root = root.left
22 else:
23 # If current node's value is less than or equal to 'p's value,
24 # the successor must be in the right subtree.
25 root = root.right
26
27 # Return the successor node
28 return successor
29
1// Definition for a binary tree node.
2class TreeNode {
3 int val;
4 TreeNode left;
5 TreeNode right;
6
7 TreeNode(int x) {
8 val = x;
9 }
10}
11
12class Solution {
13
14 /**
15 * Finds the inorder successor of a given node in a BST.
16 * The inorder successor of a node is the node with the smallest key greater than the current node's key.
17 *
18 * @param root the root of the BST
19 * @param p the target node for which we need to find the inorder successor
20 * @return the inorder successor node if exists, otherwise null
21 */
22 public TreeNode inorderSuccessor(TreeNode root, TreeNode p) {
23 TreeNode successor = null; // This will hold the successor as we traverse the tree
24
25 while (root != null) {
26 if (root.val > p.val) {
27 // If current node's value is greater than p's value,
28 // go left to find a smaller value, but closer to p's value than the current value.
29 successor = root; // The potential successor is updated
30 root = root.left;
31 } else {
32 // If current node's value is less than or equal to p's value,
33 // successor must be in the right subtree.
34 root = root.right;
35 }
36 }
37
38 return successor; // Return the successor found during traversal
39 }
40}
41
1/**
2 * The function `inorderSuccessor` finds the in-order successor of a given node `p`
3 * in a binary search tree. The in-order successor of a node is defined as the
4 * node with the smallest key greater than `p->val`. The BST property is utilized here,
5 * which implies that the in-order successor of `p` is either in `p`'s right subtree
6 * (if it exists, the leftmost node there), or it's the nearest ancestor whose left child
7 * is also an ancestor of `p`.
8 *
9 * @param root: A pointer to the root node of the binary search tree.
10 * @param p: A pointer to the node in the binary search tree whose successor is to be found.
11 * @return A pointer to the in-order successor node of `p` if it exists, or `nullptr` if `p` has no in-order successor in the tree.
12 */
13class Solution {
14public:
15 TreeNode* inorderSuccessor(TreeNode* root, TreeNode* p) {
16 TreeNode* successor = nullptr;
17
18 while (root != nullptr) {
19 // If the current node's value is greater than that of p, then the successor must be in the left subtree
20 // (or the current node itself could be a potential successor).
21 if (root->val > p->val) {
22 successor = root; // Update potential successor
23 root = root->left; // Move left to find smaller value
24 } else {
25 // If the current node's value is not greater than that of p, move to the right subtree to find a greater value.
26 // Note: This means 'root' cannot be the successor, as its value is not greater than the 'p' value
27 root = root->right;
28 }
29 }
30 // Return the last recorded potential successor which is the actual in-order successor if it exists.
31 return successor;
32 }
33};
34
1/**
2 * Finds the in-order successor of a given node in a binary search tree (BST).
3 * In a BST, the in-order successor of a node is the node with the smallest key greater than the input node's key.
4 *
5 * @param {TreeNode | null} root - The root node of the BST.
6 * @param {TreeNode | null} targetNode - The node whose in-order successor is to be found.
7 * @return {TreeNode | null} The in-order successor node if it exists, otherwise null.
8 */
9function inorderSuccessor(root: TreeNode | null, targetNode: TreeNode | null): TreeNode | null {
10 // Variable to hold the in-order successor as we traverse the tree.
11 let successor: TreeNode | null = null;
12
13 // Loop through the tree starting from the root.
14 while (root !== null) {
15 // If the current node's value is greater than the targetNode's value,
16 // then this node could be the successor. We also move to the left child,
17 // because if there is a smaller value than the current node's value that
18 // is still larger than the targetNode's value, it would be in the left subtree.
19 if (root.val > targetNode.val) {
20 successor = root;
21 root = root.left;
22 } else {
23 // If current node's value is less than or equal to the targetNode's value,
24 // we move to the right child to look for a larger value.
25 root = root.right;
26 }
27 }
28
29 // Return the found successor, which might be null if there's no successor in the tree.
30 return successor;
31}
32
Time and Space Complexity
The time complexity of the given code is O(h)
where h
is the height of the binary search tree. This is because in the worst case, the while loop will traverse from root to the leaf, following one branch and visiting each level of the tree once.
The space complexity of the given code is O(1)
because it does not use any additional space that is dependent on the size of the input tree. It only uses a fixed number of pointers regardless of the number of nodes in the tree.
Learn more about how to find time and space complexity quickly using problem constraints.
How does merge sort divide the problem into subproblems?
Recommended Readings
Everything About Trees A tree is a type of graph data structure composed of nodes and edges Its main properties are It is acyclic doesn't contain any cycles There exists a path from the root to any node Has N 1 edges where N is the number of nodes in the tree and
https algomonster s3 us east 2 amazonaws com cover_photos dfs svg Depth First Search Prereqs Recursion Review problems recursion_intro Trees problems tree_intro With a solid understanding of recursion under our belts we are now ready to tackle one of the most useful techniques in coding interviews Depth First Search DFS
Binary Search Tree Intro Definition A Binary Search Tree or BST is a rooted binary tree with the value of each internal node being greater than all the values in the respective node's left subtree and less than the ones in its right subtree An empty tree is a BST since it satisfies the
Want a Structured Path to Master System Design Too? Donāt Miss This!