Inorder predecessor and successor of a node in binary search tree

Problem

Given a Binary Search Tree, find predecessor and successor of a given node.

Problem

Examples

Example 1

graph TD
    A(15):::greenShade
    A --- B(10):::orangeShade
    A --- C(20)
    B --- D(8)
    B --- E(12):::blueShade
    C --- F(16)
    C --- G(25)

    classDef greenShade fill:#32CD32,stroke:#000,stroke-width:1px,color:#fff;
    classDef orangeShade fill:#FFA500,stroke:#000,stroke-width:1px,color:#000;
    classDef blueShade fill:#1E90FF,stroke:#000,stroke-width:1px,color:#fff;

Input: 
BST = [15, 10, 20, 8, 12, 16, 25], target = 12
Output:
Predecessor = 10, Successor = 15
Explanation:
Predecessor is the largest node less than 12, which is 10. Successor is the smallest node greater than 12, which is 15.

Example 2

graph TD
    A(15):::blueShade
    A --- B(10):::orangeShade
    A --- C(20):::greenShade
    B --- D(8)
    B --- E(12)
    C --- F(16)
    C --- G(25)

    classDef greenShade fill:#32CD32,stroke:#000,stroke-width:1px,color:#fff;
    classDef orangeShade fill:#FFA500,stroke:#000,stroke-width:1px,color:#000;
    classDef blueShade fill:#1E90FF,stroke:#000,stroke-width:1px,color:#fff;

Input: 
BST = [15, 10, 20, 8, 12, 16, 25], target = 15
Output:
Predecessor = 12, Successor = 16
Explanation:
Predecessor is the largest node less than 15, which is 12. Successor is the smallest node greater than 15, which is 16.

Solution

Before, we start with the solution:

• A predecessor in BST lies in the left subtree, and its value is the maximum of the left child if it exists.
• Similarly, a successor in BST lies in the right subtree. Its value is the minimum of the right child if it exists.
• If a given node does not have left or right children, we recursively search for its predecessor and successor by examining the parent-subtree relationship.

Method 1 - Find the min and max value

1. Traversal and Search:
   • For finding the predecessor:
     • If the target node has a left child, find the maximum value in the left subtree.
     • Otherwise, traverse up the ancestor nodes until you find an ancestor whose value is less than the target.
   • For finding the successor:
     • If the target node has a right child, find the minimum value in the right subtree.
     • Otherwise, traverse up the ancestor nodes until you find an ancestor whose value is greater than the target.
2. Binary Search Tree Properties:
   • Using BST properties, we can narrow down the range of possible nodes during traversal, which makes the solution efficient.

Code

Java

class Solution {
    public int[] findPredecessorAndSuccessor(TreeNode root, int target) {
        TreeNode predecessor = null, successor = null;
        TreeNode current = root;

        // Traverse the BST
        while (current != null) {
            if (current.val < target) {
                predecessor = current;
                current = current.right;
            } else if (current.val > target) {
                successor = current;
                current = current.left;
            } else {
                // Find predecessor in left subtree
                if (current.left != null) {
                    TreeNode temp = current.left;
                    while (temp.right != null) {
                        temp = temp.right;
                    }
                    predecessor = temp;
                }

                // Find successor in right subtree
                if (current.right != null) {
                    TreeNode temp = current.right;
                    while (temp.left != null) {
                        temp = temp.left;
                    }
                    successor = temp;
                }
                break;
            }
        }

        return new int[] {predecessor != null ? predecessor.val : -1,
                        successor != null ? successor.val : -1};
    }

    public static void main(String[] args) {
        TreeNode root = new TreeNode(15);
        root.left = new TreeNode(10);
        root.right = new TreeNode(20);
        root.left.left = new TreeNode(8);
        root.left.right = new TreeNode(12);
        root.right.left = new TreeNode(16);
        root.right.right = new TreeNode(25);

        Solution solution = new Solution();
        int[] result = solution.findPredecessorAndSuccessor(root, 12);
        System.out.println("Predecessor: " + result[0] + ", Successor: " + result[1]); // Output: Predecessor: 10, Successor: 15
    }
}

Python

class Solution:
    def findPredecessorAndSuccessor(self, root, target):
        predecessor, successor = None, None

        current = root
        while current:
            if current.val < target:
                predecessor = current
                current = current.right
            elif current.val > target:
                successor = current
                current = current.left
            else:
                # Find predecessor in left subtree
                if current.left:
                    temp = current.left
                    while temp.right:
                        temp = temp.right
                    predecessor = temp

                # Find successor in right subtree
                if current.right:
                    temp = current.right
                    while temp.left:
                        temp = temp.left
                    successor = temp
                break
            
        return predecessor.val if predecessor else None, successor.val if successor else None

# Example usage:
root = TreeNode(15)
root.left = TreeNode(10)
root.right = TreeNode(20)
root.left.left = TreeNode(8)
root.left.right = TreeNode(12)
root.right.left = TreeNode(16)
root.right.right = TreeNode(25)

solution = Solution()
print(solution.findPredecessorAndSuccessor(root, 12))  # Output: (10, 15)

Complexity

• ⏰ Time complexity: O(log n)
  • Searching for predecessor and successor involves a traversal of height h of the BST.
  • In a balanced BST, the height is log(n): O(h) = O(log(n)).
  • In the worst case (unbalanced BST), the traversal may visit all nodes: O(n).
• 🧺 Space complexity: O(h). The space required is primarily for the recursion stack, proportional to the height of the BST: O(h).

Method 2 - Find the min and max value

We use an iterative in-order traversal using stack to find the predecessor and successor:

1. Predecessor is the last node visited before the target during in-order traversal.
2. Successor is the first node visited after the target during in-order traversal.

Code

Java

class Solution {
    public int[] findPredecessorAndSuccessor(TreeNode root, int target) {
        Stack<TreeNode> stack = new Stack<>();
        TreeNode current = root, lastVisited = null;
        TreeNode predecessor = null, successor = null;

        while (!stack.isEmpty() || current != null) {
            // Push left nodes to stack
            while (current != null) {
                stack.push(current);
                current = current.left;
            }

            // Visit the node
            current = stack.pop();

            // Track predecessor (last visited node before target)
            if (lastVisited != null && lastVisited.val == target) {
                successor = current; // First node visited after target
                break;
            }
            if (current.val < target) {
                predecessor = current; // Candidate for predecessor
            }

            lastVisited = current;

            // Move to the right subtree
            current = current.right;
        }

        return new int[] {
            predecessor != null ? predecessor.val : -1,
            successor != null ? successor.val : -1
        };
    }
}

Python

class Solution:
    def findPredecessorAndSuccessor(self, root, target):
        stack = []
        current = root
        predecessor, successor = None, None
        last_visited = None

        while stack or current:
            # Push left nodes to stack
            while current:
                stack.append(current)
                current = current.left
            
            # Visit the node
            current = stack.pop()

            # Track predecessor (last visited node before target)
            if last_visited and last_visited.val == target:
                successor = current  # First node visited after target
                break
            if current.val < target:
                predecessor = current  # Candidate for predecessor
            
            last_visited = current
            
            # Move to the right subtree
            current = current.right

        return predecessor.val if predecessor else None, successor.val if successor else None

Complexity

• ⏰ Time complexity: O(n). Traversal may touch all nodes in the worst case: O(n).
• 🧺 Space complexity: O(h). Stack stores up to the height of the tree in the worst case: O(n) for an unbalanced tree and O(log(n)) for a balanced tree.