Jobs

Interviews

Discussions

Inorder Successor in BST

Medium

Asked by:

7 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

Asked by:

7 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:

What should I return if the target node `p` does not have an inorder successor in the BST?
Can the BST be empty, or can the node `p` be null?
Are the values in the BST guaranteed to be unique, or can there be duplicate values?
Is the given node `p` guaranteed to be present in the BST?
What is the range of values for the nodes in the BST, and the value of node `p`?

Brute Force Solution

Approach

The brute force way to find the inorder successor is like exhaustively searching through every single option. We essentially convert the tree into a sorted list and then find the next element after the target node's value. This guarantees we will find the successor if it exists.

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

First, we need to figure out the order of all the values in the tree. Imagine visiting every node in the tree, and writing down the value in sorted order.
Next, look through your sorted list of tree values to find the value of the node we are interested in.
Once you find the value, look at the very next value in the list. That value is the inorder successor.
If the value we are looking for is the last value in the sorted list, then there is no inorder successor.

Code Implementation

def inorder_successor_brute_force(root, node):
    def inorder_traversal(current_node, sorted_list):
        if current_node is None:
            return

        inorder_traversal(current_node.left, sorted_list)
        sorted_list.append(current_node)
        inorder_traversal(current_node.right, sorted_list)

    sorted_nodes = []
    # We need to flatten the tree to find the inorder successor.
    inorder_traversal(root, sorted_nodes)

    node_found = False
    for index, current_node in enumerate(sorted_nodes):
        if current_node == node:
            node_found = True

            # The next node in the sorted list is the successor.
            if index + 1 < len(sorted_nodes):
                return sorted_nodes[index + 1]

    # If we reach here, there is no inorder successor
    return None

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

O(n) – The first step involves traversing the entire tree to create a sorted list of node values, which takes O(n) time, where n is the number of nodes in the tree. Subsequently, the algorithm iterates through this sorted list to find the target node's value, which also takes O(n) time in the worst case. Finally, accessing the next element in the list to find the successor takes O(1) time. Therefore, the dominant factor is the traversal of the tree and the search in the created array, both linear with respect to the number of nodes, resulting in a total time complexity of O(n).

Space Complexity

O(N) – The described brute force approach involves creating a sorted list of all node values in the BST. This list requires space proportional to the number of nodes in the tree, denoted as N. Therefore, the auxiliary space used is dependent on the size of the input tree; specifically, an array of size N is used to store the sorted node values. Consequently, the space complexity is O(N).

Optimal Solution

Approach

The goal is to find the node that comes right after a given node in a binary search tree when you visit the nodes in increasing order. We can find this 'next' node efficiently by cleverly navigating the tree, focusing on the right subtree or the path back up to the root.

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

First, check if the node has a right child. If it does, the inorder successor is the leftmost node in that right subtree. So, go right once, and then keep going left as far as you can.
If the node does *not* have a right child, then the inorder successor is one of its ancestors. We need to go up the tree.
Go up the tree, checking each parent node. The inorder successor is the first parent node that the original node is in the *left* subtree of.
If you reach the root of the tree and never find such a parent, it means the original node was the last node in the inorder traversal, so it has no inorder successor.

Code Implementation

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

def find_inorder_successor(node):
    if node.right:
        # Node has right child, find leftmost in right subtree.
        return find_leftmost_node(node.right)

    # Node has no right child, find the ancestor.
    return find_ancestor_successor(node)

def find_leftmost_node(node):
    current_node = node
    while current_node.left:
        current_node = current_node.left
    return current_node

def find_ancestor_successor(node):
    current_node = node
    while current_node.parent:
        parent_node = current_node.parent
        #Check if current node is in the left subtree of parent
        if parent_node.left == current_node:
            return parent_node

        current_node = parent_node
    # Node is the rightmost node, no inorder successor
    return None

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

O(h) – The algorithm involves traversing down the tree to find the leftmost node in the right subtree (if the node has a right child) or traversing up the tree to find the first ancestor for which the given node is in its left subtree. In the worst-case scenario, both traversals could potentially involve visiting nodes along a path from the given node to the deepest leaf in its right subtree or the root of the tree. The height (h) of the tree determines the maximum number of nodes visited in these traversals. Therefore, the time complexity is proportional to the height of the tree, resulting in O(h). For a balanced BST, h is log(n), and for a skewed tree, h can be n.

Space Complexity

O(H) – The space complexity is determined by the maximum depth of the call stack during the ancestor search when the node does not have a right child. In the worst case, we might traverse all the way up to the root of the tree if the target node is the rightmost node, where H is the height of the tree. Therefore, the maximum number of stack frames stored due to the recursive calls would be proportional to the height of the tree. In a balanced tree, H is log(N), and in a skewed tree, H could be N, where N is the number of nodes in the BST.

Edge Cases

Case	How to Handle
Root is null	Return null immediately since an empty tree has no successor.
Node p is null	Return null immediately since a null node has no successor.
Node p is the rightmost node in the tree (no successor exists)	The algorithm should return null when no node is greater than p.
Node p has a right subtree	The inorder successor is the smallest node in p's right subtree; locate using a left-most descent from the right child.
Node p does not have a right subtree, and it's somewhere in the middle of the tree	The algorithm should traverse up the tree to find the first ancestor that p is in its left subtree.
Tree with only one node (root) and p is the root	Return null since the root is the only node, and thus has no successor.
BST with skewed structure (e.g., all nodes are left children)	The algorithm should still correctly find the successor by traversing up the skewed tree.
Duplicate values in the BST	The algorithm should still correctly identify the inorder successor based on the smallest value greater than p.val.

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 should I return if the target node `p` does not have an inorder successor in the BST?
Can the BST be empty, or can the node `p` be null?
Are the values in the BST guaranteed to be unique, or can there be duplicate values?
Is the given node `p` guaranteed to be present in the BST?
What is the range of values for the nodes in the BST, and the value of node `p`?

Brute Force Solution

Approach

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

First, we need to figure out the order of all the values in the tree. Imagine visiting every node in the tree, and writing down the value in sorted order.
Next, look through your sorted list of tree values to find the value of the node we are interested in.
Once you find the value, look at the very next value in the list. That value is the inorder successor.
If the value we are looking for is the last value in the sorted list, then there is no inorder successor.

Code Implementation

def inorder_successor_brute_force(root, node):
    def inorder_traversal(current_node, sorted_list):
        if current_node is None:
            return

        inorder_traversal(current_node.left, sorted_list)
        sorted_list.append(current_node)
        inorder_traversal(current_node.right, sorted_list)

    sorted_nodes = []
    # We need to flatten the tree to find the inorder successor.
    inorder_traversal(root, sorted_nodes)

    node_found = False
    for index, current_node in enumerate(sorted_nodes):
        if current_node == node:
            node_found = True

            # The next node in the sorted list is the successor.
            if index + 1 < len(sorted_nodes):
                return sorted_nodes[index + 1]

    # If we reach here, there is no inorder successor
    return None

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

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

First, check if the node has a right child. If it does, the inorder successor is the leftmost node in that right subtree. So, go right once, and then keep going left as far as you can.
If the node does *not* have a right child, then the inorder successor is one of its ancestors. We need to go up the tree.
Go up the tree, checking each parent node. The inorder successor is the first parent node that the original node is in the *left* subtree of.
If you reach the root of the tree and never find such a parent, it means the original node was the last node in the inorder traversal, so it has no inorder successor.

Code Implementation

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

def find_inorder_successor(node):
    if node.right:
        # Node has right child, find leftmost in right subtree.
        return find_leftmost_node(node.right)

    # Node has no right child, find the ancestor.
    return find_ancestor_successor(node)

def find_leftmost_node(node):
    current_node = node
    while current_node.left:
        current_node = current_node.left
    return current_node

def find_ancestor_successor(node):
    current_node = node
    while current_node.parent:
        parent_node = current_node.parent
        #Check if current node is in the left subtree of parent
        if parent_node.left == current_node:
            return parent_node

        current_node = parent_node
    # Node is the rightmost node, no inorder successor
    return None

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Root is null	Return null immediately since an empty tree has no successor.
Node p is null	Return null immediately since a null node has no successor.
Node p is the rightmost node in the tree (no successor exists)	The algorithm should return null when no node is greater than p.
Node p has a right subtree	The inorder successor is the smallest node in p's right subtree; locate using a left-most descent from the right child.
Node p does not have a right subtree, and it's somewhere in the middle of the tree	The algorithm should traverse up the tree to find the first ancestor that p is in its left subtree.
Tree with only one node (root) and p is the root	Return null since the root is the only node, and thus has no successor.
BST with skewed structure (e.g., all nodes are left children)	The algorithm should still correctly find the successor by traversing up the skewed tree.
Duplicate values in the BST	The algorithm should still correctly identify the inorder successor based on the smallest value greater than p.val.