Jobs

Interviews

Discussions

Inorder Successor in BST

Medium

Microsoft

0 views

Topics:

TreesBinary Search

Given the root of a binary search tree (BST) and a node p in the tree, find the in-order successor of the node p in the BST. If the in-order successor does not exist, return null.

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

Example 1:

Input: root = [5,3,6,2,4,null,null,1], p = 6
Output: null
Explanation: There is no in-order successor of the current node, so the answer is null.

Example 2:

Input: root = [5,3,6,2,4,null,null,1], p = 1
Output: 2
Explanation: 1's in-order successor node is 2. Note that the successor could be a descendant of the node.

Example 3:

Input: root = [2,1,3], p = 1
Output: 2

Constraints:

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

Inorder Successor in BST

Medium

Microsoft

0 views

Topics:

TreesBinary Search

Given the root of a binary search tree (BST) and a node p in the tree, find the in-order successor of the node p in the BST. If the in-order successor does not exist, return null.

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

Example 1:

Input: root = [5,3,6,2,4,null,null,1], p = 6
Output: null
Explanation: There is no in-order successor of the current node, so the answer is null.

Example 2:

Input: root = [5,3,6,2,4,null,null,1], p = 1
Output: 2
Explanation: 1's in-order successor node is 2. Note that the successor could be a descendant of the node.

Example 3:

Input: root = [2,1,3], p = 1
Output: 2

Constraints:

The number of nodes in the tree is in the range [1, 10⁴].
-10⁵ <= Node.val <= 10⁵
All the values of 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:

Can the BST be empty, and if so, what should I return?
What should I return if the given node 'p' does not have an inorder successor in the BST?
Are the keys in the BST guaranteed to be unique, or could there be duplicate keys?
Is the given node 'p' guaranteed to be in the BST?
What is the range of values that the nodes in the BST can take?

Brute Force Solution

Approach

To find the inorder successor, the brute force method involves looking at all nodes in the tree. We examine each node and figure out where it fits in relation to the target node, ultimately identifying the next biggest value.

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

First, travel through the entire tree and collect all the node values into a simple list.
Sort this list of values from smallest to largest.
Now, find the target node's value in this sorted list.
Once found, look at the very next value in the list.
If there is a next value, that's the inorder successor we're looking for. Return the node with that value.
If there isn't a next value (meaning the target node had the largest value in the tree), then there's no inorder successor. Return nothing.

Code Implementation

def inorder_successor_brute_force(root, target_node):

    node_values = []

    def inorder_traversal(node):
        if node:
            inorder_traversal(node.left)
            node_values.append(node.val)
            inorder_traversal(node.right)

    inorder_traversal(root)

    # Collect all node values.

    node_values.sort()

    # Find the target node's value in the sorted list.
    try:
        target_index = node_values.index(target_node.val)
    except ValueError:
        return None

    # Determine if there is a next value.
    if target_index + 1 < len(node_values):

        successor_value = node_values[target_index + 1]

        def find_node(root, value):
            if not root:
                return None
            if root.val == value:
                return root
            left_result = find_node(root.left, value)
            if left_result:
                return left_result
            return find_node(root.right, value)

        # Find the node with the successor value.
        return find_node(root, successor_value)
    else:
        # Target node had the largest value in the tree.
        return None

Big(O) Analysis

Time Complexity

O(n log n) – The algorithm first traverses the entire tree to collect all n node values into a list, which takes O(n) time. Then, it sorts this list of n values, which typically uses an efficient comparison-based sorting algorithm like merge sort or quicksort, resulting in O(n log n) time complexity. After sorting, finding the target node's value in the sorted list takes O(n) in the worst case if we just iterate over the sorted array. Finally, accessing the next element is O(1). Therefore the dominant cost is sorting the array making the time complexity O(n log n).

Space Complexity

O(N) – The provided solution first traverses the entire tree and stores all N node values into a list. Then this list is sorted in place. The dominant space complexity comes from storing all node values in the list which requires space proportional to the number of nodes in the tree, N. Therefore, the auxiliary space complexity is O(N).

Optimal Solution

Approach

To find the next biggest value in a special tree (a Binary Search Tree) after a specific value, we can use the structure of the tree to guide our search. Instead of checking the whole tree, we can follow a clever path that quickly leads us to the answer.

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

Start at the very top of the tree.
Go down the tree, comparing each value we see to the value we're looking for.
If the current value is bigger than the value we're looking for, remember it as a possible answer and go left, because the next biggest value could be somewhere smaller.
If the current value is smaller or equal to the value we're looking for, go right, because the next biggest value must be somewhere larger.
Keep doing this until you can't go any further down the tree.
The last 'possible answer' you remembered is the next biggest value in the tree after the one you were looking for.

Code Implementation

class TreeNode:
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None

def inorder_successor(root, node):
    potential_answer = None

    while root:
        if root.value > node.value:
            # This node could be the answer, so store it.
            potential_answer = root
            root = root.left

        elif root.value <= node.value:
            # Go right since successor must be larger.
            root = root.right

    return potential_answer

Big(O) Analysis

Time Complexity

O(h) – The algorithm traverses a path from the root of the Binary Search Tree to a node or a leaf. In the worst case, this path could be as long as the height (h) of the tree. Each step involves a constant amount of comparison operations. Therefore, the time complexity is directly proportional to the height of the tree, which is O(h). In a balanced BST, h is log(n), but in a skewed BST, h can be n, where n is the number of nodes.

Space Complexity

O(1) – The algorithm iteratively traverses the binary search tree, updating a 'possible answer' variable as it goes. No auxiliary data structures that scale with the input size (N, where N is the number of nodes in the tree) are created. The space used to store the 'possible answer' is constant, irrespective of the tree's size, resulting in constant auxiliary space complexity.

Edge Cases

Case	How to Handle
Null or empty BST	Return null immediately as there is no successor in an empty tree.
Node has no inorder successor (rightmost node)	Return null when traversing up the tree and no larger parent is found.
Node is the root of the BST	The logic to find the successor still applies regardless of the starting node's position in the tree.
Node has a right subtree	Return the minimum value of the right subtree.
BST contains duplicate values; node has duplicates.	Handle this case correctly by finding the smallest value larger than node.val, which might involve looking at the right subtree or ancestor nodes.
The target node itself is null.	Return null since there is no node to find the successor of.
BST with only one node and that is the target.	Return null, because that single node has no successor.
Very deep BST, potential stack overflow with recursive solutions	Consider an iterative approach to avoid stack overflow issues with very large trees.

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:

Can the BST be empty, and if so, what should I return?
What should I return if the given node 'p' does not have an inorder successor in the BST?
Are the keys in the BST guaranteed to be unique, or could there be duplicate keys?
Is the given node 'p' guaranteed to be in the BST?
What is the range of values that the nodes in the BST can take?

Brute Force Solution

Approach

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

First, travel through the entire tree and collect all the node values into a simple list.
Sort this list of values from smallest to largest.
Now, find the target node's value in this sorted list.
Once found, look at the very next value in the list.
If there is a next value, that's the inorder successor we're looking for. Return the node with that value.
If there isn't a next value (meaning the target node had the largest value in the tree), then there's no inorder successor. Return nothing.

Code Implementation

def inorder_successor_brute_force(root, target_node):

    node_values = []

    def inorder_traversal(node):
        if node:
            inorder_traversal(node.left)
            node_values.append(node.val)
            inorder_traversal(node.right)

    inorder_traversal(root)

    # Collect all node values.

    node_values.sort()

    # Find the target node's value in the sorted list.
    try:
        target_index = node_values.index(target_node.val)
    except ValueError:
        return None

    # Determine if there is a next value.
    if target_index + 1 < len(node_values):

        successor_value = node_values[target_index + 1]

        def find_node(root, value):
            if not root:
                return None
            if root.val == value:
                return root
            left_result = find_node(root.left, value)
            if left_result:
                return left_result
            return find_node(root.right, value)

        # Find the node with the successor value.
        return find_node(root, successor_value)
    else:
        # Target node had the largest value in the tree.
        return None

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

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

Start at the very top of the tree.
Go down the tree, comparing each value we see to the value we're looking for.
If the current value is bigger than the value we're looking for, remember it as a possible answer and go left, because the next biggest value could be somewhere smaller.
If the current value is smaller or equal to the value we're looking for, go right, because the next biggest value must be somewhere larger.
Keep doing this until you can't go any further down the tree.
The last 'possible answer' you remembered is the next biggest value in the tree after the one you were looking for.

Code Implementation

class TreeNode:
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None

def inorder_successor(root, node):
    potential_answer = None

    while root:
        if root.value > node.value:
            # This node could be the answer, so store it.
            potential_answer = root
            root = root.left

        elif root.value <= node.value:
            # Go right since successor must be larger.
            root = root.right

    return potential_answer

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Null or empty BST	Return null immediately as there is no successor in an empty tree.
Node has no inorder successor (rightmost node)	Return null when traversing up the tree and no larger parent is found.
Node is the root of the BST	The logic to find the successor still applies regardless of the starting node's position in the tree.
Node has a right subtree	Return the minimum value of the right subtree.
BST contains duplicate values; node has duplicates.	Handle this case correctly by finding the smallest value larger than node.val, which might involve looking at the right subtree or ancestor nodes.
The target node itself is null.	Return null since there is no node to find the successor of.
BST with only one node and that is the target.	Return null, because that single node has no successor.
Very deep BST, potential stack overflow with recursive solutions	Consider an iterative approach to avoid stack overflow issues with very large trees.