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.