Leetcode 510. Inorder Successor in BST II
Problem Explanation
A binary search tree is a node-based binary tree data structure which has the following properties: the left sub-tree of a node contains only nodes with keys less than the nodeโs key, the right sub-tree of a node contains only nodes with keys greater than the nodeโs key and both the left and right sub-trees must also be binary search trees.
The problem here is given a binary search tree and a node in it, your task is to find the in-order successor of the node. The in-order successor of a node in a binary search tree is the next node in in-order sequence of the tree. If the provided node has no in-order successor in the tree, you should return null.
The problem specifies that you will have direct access to the node but not to the root of the tree and each node will have a reference to its parent node. It's also guaranteed that the values of the tree are unique.
Solution Approach
The in-order successor of a node can be found as follows:
-
If the node has right child, then the in-order successor of the node will be the left most node in right subtree of the node.
-
If the node doesn't have a right child, then we start from the parent node and keep moving up until we see a node which is left child of its parent node. Such a node's parent will be the in-order successor. If we reach root of tree while moving up and do not find an ancestor which is left child of its parent, then given node has no in-order successor, i.e., it is the last node in the in-order traversal of the tree.
Python Solution
1 2python 3class Solution: 4 def inorderSuccessor(self, node): 5 # If right child exists, inorder Successor will be the left most element in right child 6 if node.right: 7 node = node.right 8 while node.left: 9 node = node.left 10 return node 11 12 # If right child does not exist, Inorder Successor will be one of the ancestors 13 while node.parent and node.parent.left != node: 14 node = node.parent 15 return node.parent
Java Solution
1 2java 3class Solution { 4 public Node inorderSuccessor(Node node) { 5 if (node.right != null) { 6 node = node.right; 7 while (node.left != null) { 8 node = node.left; 9 } 10 return node; 11 } 12 while (node.parent != null && node.parent.left != node) { 13 node = node.parent; 14 } 15 return node.parent; 16 } 17}
C++ Solution
1 2c++ 3class Solution { 4public: 5 Node* inorderSuccessor(Node* node) { 6 if (node->right) { 7 node = node->right; 8 while (node->left) 9 node = node->left; 10 return node; 11 } 12 13 while (node->parent && node->parent->left != node) 14 node = node->parent; 15 return node->parent; 16 } 17};
C# Solution
1 2csharp 3public class Solution { 4 public Node InorderSuccessor(Node node) { 5 if (node.right != null) { 6 node = node.right; 7 while (node.left != null) 8 node = node.left; 9 return node; 10 } 11 while (node.parent != null && node.parent.left != node) { 12 node = node.parent; 13 } 14 return node.parent; 15 } 16}
JavaScript Solution
1 2js 3class Solution{ 4 inorderSuccessor(node) { 5 if(node.right) { 6 node = node.right; 7 while(node.left) 8 node = node.left; 9 return node; 10 } 11 12 while(node.parent && node.parent.left !== node) { 13 node = node.parent; 14 } 15 return node.parent; 16 } 17}
There are no extra space requirements for this solution and the time complexity is O(h)
, where h
is the height of the tree as we are traversing the tree from a given node either towards the left most node of its right subtree or towards the parent.## Explanation
The Python, Java, JavaScript, C++ and C# solutions given here follow the same approach. Firstly, it's checked if the given node has a right child. If it does, the leftmost child of the right subtree gets identified as the next in-order successor.
If the node doesn't have a right child, it continues up the tree (using the parent pointer) until it finds an element that is a left child of its parent. This parent becomes the in-order successor of our original node.
For locating the in-order successor of nodes that have a right child, at most h (height of the tree) nodes are visited. Similarly, for nodes that don't have a right child, at most h ancestors (or less) need to be visited. Hence, the worst case time complexity of this process is O(h).
It must be noted that in these solutions, we've assumed that each node has a reference to its parent. If the parent's reference isn't available, then the problem would be harder to solve, especially when the node doesn't have a right child. In this case, you'll need access to the root of the tree to solve the problem.
In conclusion, searching for an in-order successor in a binary search tree is a common task in tree manipulations. Efficient solutions for this problem are crucial, particularly when dealing with large amounts of data. These Python, Java, JavaScript, C++ and C# solutions provide fast and efficient ways to solve this 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.