Inorder Successor in BST

 

1. Clarify the problem: Before diving into solving the problem, let's clarify the requirements:

  • We are given a binary search tree (BST) and a target node.
  • We need to find the in-order successor of the given target node in the BST.
  • In-order successor of a node is the node that appears immediately after the given node in the in-order traversal of the BST.

2. Analyze the problem: To solve this problem, we can follow a recursive approach. We'll traverse the BST while keeping track of the potential successor. When we find the target node, we'll update the successor to the current node and continue traversing the right subtree to find the minimum node.

3. Design an algorithm: Here is the algorithm to solve the problem:

  1. Initialize a variable successor to None.
  2. Define a recursive function findSuccessor(node, target):
    • If node is None, return successor.
    • If node value is greater than target, set successor to node and recursively call findSuccessor(node.left, target).
    • If node value is less than or equal to target, recursively call findSuccessor(node.right, target).
  3. Return the result of findSuccessor(root, target).

4. Explain your approach: The approach involves traversing the BST using a recursive function. We keep track of the potential successor as we traverse the tree. When we find the target node, we update the successor to the current node and continue traversing the right subtree to find the minimum node. This is because in-order traversal visits the left subtree, then the current node, and finally the right subtree.

5. Write clean and readable code:

python
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right


def inorderSuccessor(root, target):
    successor = None

    def findSuccessor(node, target):
        nonlocal successor

        if node is None:
            return successor

        if node.val > target:
            successor = node
            return findSuccessor(node.left, target)
        else:
            return findSuccessor(node.right, target)

    return findSuccessor(root, target)

6. Test your code: Let's test the code with some test cases:

  • Test case 1:

    • root = TreeNode(6) /
      TreeNode(2) TreeNode(8) / \ /
      TreeNode(0) TreeNode(4) TreeNode(9)
      TreeNode(3)
    • target = 4
    • The expected output is TreeNode(6) because in the in-order traversal, the next node after 4 is 6.

  • Test case 2:

    • root = TreeNode(6) /
      TreeNode(2) TreeNode(8) / \ /
      TreeNode(0) TreeNode(4) TreeNode(9)
      TreeNode(3)
    • target = 9
    • The expected output is None because the target node is the rightmost node in the tree, and there is no node after it in the in-order traversal.
python
# Test case 1
root = TreeNode(6)
root.left = TreeNode(2)
root.right = TreeNode(8)
root.left.left = TreeNode(0)
root.left.right = TreeNode(4)
root.right.right = TreeNode(9)
root.left.right.left = TreeNode(3)

target1 = root.left.right  # Node with value 4
print(inorderSuccessor(root, target1).val)  # Expected output: 6

# Test case 2
target2 = root.right.right  # Node with value 9
print(inorderSuccessor(root, target2))  # Expected output: None

7. Optimize if necessary: The current solution has a time complexity of O(h), where h is the height of the BST. In the worst case, the height of the BST can be equal to the number of nodes in the tree, resulting in a time complexity of O(n). There is no obvious optimization opportunity for this problem.

8. Handle error cases: The code assumes that the input root is a valid BST and the target node is present in the BST. If the root is None or the target node is not found in the BST, the behavior of the code may not be as expected. We can add checks at the beginning to handle these cases and return None.

9. Discuss complexity analysis: The time complexity of the solution is O(h), where h is the height of the BST. In the worst case, the height of the BST can be equal to the number of nodes in the tree, resulting in a time complexity of O(n). The space complexity is O(h) due to the recursive calls, where h is the height of the BST. In the worst case, the space complexity can be O(n) if the tree is skewed.

Next Post Previous Post