Leetcode 285. Inorder Successor in BST
Problem Description
We are given a binary search tree and a node (let's call it p
) in it. The task is to find the in-order successor of p
in the binary search tree. The in-order successor of a node p
is the node with the smallest key greater than p.val
.
If the given node p
does not have an in-order successor in the tree, we should return null
or None
.
Let's go through an example:
Input: root = [2,1,3], p = 1
In this case, the binary search tree is like this:
1 2 3 2 4 / \ 51 3
The in-order traversal of the tree gives us a sorted list of nodes: [1, 2, 3]. For p
which equals to 1, the in-order successor is 2. Therefore, the output is 2.
Solution Approach
To solve this problem, we can use a recursive approach with binary search property in mind.
Here is the core idea:
- If
root
equalsnull
, then returnnull
. Because there is no node in the tree. - If
root
's value (root.val
) is less than or equal top.val
, the in-order successor can only be in the right subtree. So we should check the right subtree. - Otherwise, there could be two situations:
- There is an in-order successor in the left subtree.
- There is no in-order successor in the left subtree, so the
root
node itself is the in-order successor.
With this approach, we need to traverse at most h
nodes (with h
being the height of the tree), so the time complexity is O(h). And the space complexity is O(h) due to the function call stack (in case of a skewed binary tree).
Python Solution
1 2python 3class TreeNode: 4 def __init__(self, x): 5 self.val = x 6 self.left = None 7 self.right = None 8 9class Solution: 10 def inorderSuccessor(self, root: 'TreeNode', p: 'TreeNode') -> 'TreeNode': 11 if root is None: 12 return None 13 if root.val <= p.val: 14 return self.inorderSuccessor(root.right, p) 15 16 left = self.inorderSuccessor(root.left, p) 17 return left if left is not None else root
Java Solution
1
2java
3public class TreeNode {
4 int val;
5 TreeNode left;
6 TreeNode right;
7 TreeNode(int x) { val = x; }
8}
9
10public class Solution {
11 public TreeNode inorderSuccessor(TreeNode root, TreeNode p) {
12 if (root == null)
13 return null;
14 if (root.val <= p.val)
15 return inorderSuccessor(root.right, p);
16
17 TreeNode left = inorderSuccessor(root.left, p);
18 return left != null ? left : root;
19 }
20}
JavaScript Solution
1 2javascript 3function TreeNode(val, left, right) { 4 this.val = (val===undefined ? 0 : val) 5 this.left = (left===undefined ? null : left) 6 this.right = (right===undefined ? null : right) 7} 8 9var inorderSuccessor = function(root, p) { 10 if (root === null) 11 return null; 12 if (root.val <= p.val) 13 return inorderSuccessor(root.right, p); 14 15 const left = inorderSuccessor(root.left, p); 16 return left !== null ? left : root; 17};
C++ Solution
1
2cpp
3struct TreeNode {
4 int val;
5 TreeNode *left;
6 TreeNode *right;
7 TreeNode(int x) : val(x), left(NULL), right(NULL) {}
8};
9
10class Solution {
11public:
12 TreeNode* inorderSuccessor(TreeNode* root, TreeNode* p) {
13 if (root == nullptr)
14 return nullptr;
15 if (root->val <= p->val)
16 return inorderSuccessor(root->right, p);
17
18 TreeNode* left = inorderSuccessor(root->left, p);
19 return left != nullptr ? left : root;
20 }
21};
C# Solution
1
2csharp
3public class TreeNode {
4 public int val;
5 public TreeNode left;
6 public TreeNode right;
7 public TreeNode(int x) { val = x; }
8}
9
10public class Solution {
11 public TreeNode InorderSuccessor(TreeNode root, TreeNode p) {
12 if (root == null)
13 return null;
14 if (root.val <= p.val)
15 return InorderSuccessor(root.right, p);
16
17 TreeNode left = InorderSuccessor(root.left, p);
18 return left != null ? left : root;
19 }
20}
Swift Solution
1
2swift
3public class TreeNode {
4 public var val: Int
5 public var left: TreeNode?
6 public var right: TreeNode?
7 public init(_ val: Int) {
8 self.val = val
9 self.left = nil
10 self.right = nil
11 }
12}
13
14class Solution {
15 func inorderSuccessor(_ root: TreeNode?, _ p: TreeNode) -> TreeNode? {
16 if root == nil {
17 return nil
18 }
19 if root!.val <= p.val {
20 return inorderSuccessor(root!.right, p)
21 }
22
23 let left = inorderSuccessor(root!.left, p)
24 return left != nil ? left : root
25 }
26}
In the Swift solution, we define a TreeNode class with three properties: val
, left
, and right
. The inorderSuccessor
function uses the same logic described previously. We first check if the root
is equal to nil
. If it is, we return nil
. If the root
's val
is less than or equal to p.val
, we recursively call the function on the right
node. Otherwise, we recursively call the function on the left
node. If the call to the left node returns nil
(which means the left subtree does not have an in-order successor), we return the root
.
That wraps up our discussion on finding the In-Order Successor in a Binary Search Tree. We have covered the problem, the approach to solve it and we have shown solutions in Python, JavaScript, Java, C++, C#, and Swift. We hope this article has been helpful and has given you a firm understanding of this common interview problem.
Got a question?ย Ask the Teaching Assistantย anything you don't understand.
Still not clear? Ask in the Forum, ย Discordย orย Submitย the part you don't understand to our editors.