Inorder Successor in BST II

Medium

Arista Networks

1 view

Topics:

Trees

Given a node in a binary search tree, return the in-order successor of that node in the BST. If that node has no in-order successor, return null.

The successor of a node node is the node with the smallest key greater than node.val.

You will have direct access to the node but not to the root of the tree. Each node will have a reference to its parent node. Below is the definition for Node:

class Node {
    public int val;
    public Node left;
    public Node right;
    public Node parent;
}

Follow up:

Could you solve it without looking up any of the node's values?

Example 1:

Input: node = [2,1,3]
Output: 3
Explanation: 2's in-order successor node is 3. Note that both the node and the return value are Node type.

Example 2:

Input: node = [5,3,6,2,4,null,null,1]
Output: 6
Explanation: 5's in-order successor node is 6.

Example 3:

Input: node = [6,2,8,0,4,7,9,null,null,3,5]
Output: 7
Explanation: 6's in-order successor node is 7.

Constraints:

The number of nodes in the tree is in the range [1, 10⁴].
-10⁵ <= Node.val <= 10⁵
All the values in the tree are unique.

Inorder Successor in BST II

Medium

Arista Networks

1 view

Topics:

Trees

Given a node in a binary search tree, return the in-order successor of that node in the BST. If that node has no in-order successor, return null.

The successor of a node node is the node with the smallest key greater than node.val.

You will have direct access to the node but not to the root of the tree. Each node will have a reference to its parent node. Below is the definition for Node:

class Node {
    public int val;
    public Node left;
    public Node right;
    public Node parent;
}

Follow up:

Could you solve it without looking up any of the node's values?

Example 1:

Input: node = [2,1,3]
Output: 3
Explanation: 2's in-order successor node is 3. Note that both the node and the return value are Node type.

Example 2:

Input: node = [5,3,6,2,4,null,null,1]
Output: 6
Explanation: 5's in-order successor node is 6.

Example 3:

Input: node = [6,2,8,0,4,7,9,null,null,3,5]
Output: 7
Explanation: 6's in-order successor node is 7.

Constraints:

The number of nodes in the tree is in the range [1, 10⁴].
-10⁵ <= Node.val <= 10⁵
All the values in the tree are unique.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the range of values for the nodes in the BST?
Can the input node 'p' be null or not present in the tree?
What should I return if 'p' is the rightmost node in the tree (i.e., it has no inorder successor)? Should I return null, or is there a sentinel value?
Does each node in the BST have a 'parent' pointer as described in the problem, and can I rely on its correctness?
Are all node values in the BST guaranteed to be unique?

Brute Force Solution

Approach

Imagine searching for a name in a phone book but without any alphabetical order. The brute force method here means looking at every single name one by one until you find the one that comes right after the given name in the overall order of the phone book.

Here's how the algorithm would work step-by-step:

Start at the very beginning of the phone book (the root of the tree).
Go through every single entry (node) in the entire phone book (tree).
For each entry, check if it is larger than the given name.
If it is larger, keep track of it, and compare it with other larger names you find later.
After going through the entire phone book, pick the smallest name among all the names that were larger than the given name. That is the name that comes right after it.

Code Implementation

def inorder_successor_brute_force(node):
    successor_node = None
    current_node = get_leftmost_ancestor(node)

    while current_node:
        # Found the successor, which must be greater than node.
        if current_node.val > node.val:
            # Need to find smallest node that is larger.
            if successor_node is None or current_node.val < successor_node.val:
                successor_node = current_node

        current_node = get_next_node(current_node)

    return successor_node

def get_leftmost_ancestor(node):
    current_node = node
    while current_node.left:
        current_node = current_node.left

    while current_node.parent:
        current_node = current_node.parent

    return current_node

def get_next_node(current_node):
    if current_node.right:
        current_node = current_node.right
        while current_node.left:
            current_node = current_node.left
        return current_node
    else:
        parent_node = current_node.parent

        # Traverse the parent until we find node that is the left child of its parent.
        while parent_node and current_node == parent_node.right:
            current_node = parent_node
            parent_node = current_node.parent

        return parent_node

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

O(n) – The described algorithm visits every node in the binary search tree once to find the inorder successor. The size of the input is defined as n, representing the total number of nodes in the tree. Because the algorithm iterates through each node to perform the comparison, it performs a constant amount of work on each of the n nodes, irrespective of the tree's structure. Therefore, the time complexity is directly proportional to the number of nodes, resulting in O(n) time complexity.

Space Complexity

O(1) – The provided algorithm iterates through the tree and keeps track of the smallest node larger than the given node. It uses a single variable (or a small fixed number of variables) to store the potential successor. The space used does not depend on the number of nodes (N) in the tree. Therefore, the auxiliary space complexity is constant.

Optimal Solution

Approach

The goal is to find the next largest node in a binary search tree given a specific node. We can avoid traversing the entire tree by intelligently using the structure of the tree and the 'parent' pointers if they exist.

Here's how the algorithm would work step-by-step:

First, check if the given node has a right child. If it does, the successor is the leftmost node in that right subtree. Find that node.
If the node does not have a right child, we need to go up the tree. Go up to the node's parent.
Keep going up the tree (to the parent's parent, and so on) until you find a node that is the *left* child of its parent. The successor is that parent.
If you reach the root and still haven't found a node that's a left child, it means the original node was the largest in the tree and thus has no successor. In this case, return nothing.

Code Implementation

class Node:
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None
        self.parent = None

def inorder_successor(node):
    if node.right:
        # If there's a right child, successor is leftmost node in right subtree
        node_with_right_subtree = node.right
        while node_with_right_subtree.left:
            node_with_right_subtree = node_with_right_subtree.left
        return node_with_right_subtree

    # If no right child, we need to find the ancestor.
    current_node = node
    while current_node.parent:

        parent_node = current_node.parent

        # Moving up until node is a left child
        if parent_node.left == current_node:
            return parent_node

        # Need to traverse upward
        current_node = parent_node

    # No successor if we reach the root.
    return None

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

O(h) – The time complexity is determined by the height 'h' of the BST. In the best case (complete or balanced BST), finding the leftmost node in the right subtree (if a right child exists) takes O(h) time. In the worst case (skewed BST), traversing up the tree to find the first ancestor that is a left child can also take O(h) time, where h approaches n, the number of nodes. Therefore, the overall time complexity is O(h).

Space Complexity

O(1) – The algorithm uses a constant amount of extra space. It iterates upwards using parent pointers without creating any auxiliary data structures that scale with the number of nodes (N). The space used for potentially storing a few node pointers during traversal does not depend on the size of the tree. Therefore, the space complexity is constant.

Edge Cases

Case	How to Handle
Null root node	Return null immediately as there's no BST to traverse.
Node is the rightmost node in the tree (no inorder successor)	Return null, indicating there is no inorder successor.
Node has a right subtree but the successor is at the bottom left of it	Traverse down the left-most node of the right subtree to find the inorder successor.
Node has no right subtree, and the successor is an ancestor	Iterate upwards using the parent pointer until finding an ancestor that is a left child.
BST with only one node, target is that node	The inorder successor should be null because that is the rightmost node.
Deeply skewed BST to the left (worst-case height)	The upward traversal using the parent pointer might take O(N) time in the worst case.
Node has a right subtree, but that right subtree has negative values which may result in integer overflow	Handle negative values within the right subtree correctly when comparing node values.
Duplicate keys in the BST (violates BST property)	Handle the case where the node's value is equal to the inorder successor and the successor is on the left or right side of the BST.