DSA 450 Notes

Problem Statement

Given a BST and a node, find the inorder successor and inorder predecessor of the given node.

Inorder Successor: The next node in inorder traversal (smallest node greater than the given node)
Inorder Predecessor: The previous node in inorder traversal (largest node smaller than the given node)

Example:

        20
       /  \
      8    22
     / \
    4   12
       /  \
      10   14

For node 8:
  Predecessor: 4 (largest smaller than 8)
  Successor: 10 (smallest greater than 8)

For node 12:
  Predecessor: 10
  Successor: 14

Approach 1: Brute Force (Inorder Traversal)

Intuition

Perform complete inorder traversal to get sorted array. Find the target in the array, then predecessor is the previous element and successor is the next element.

Algorithm

Perform inorder traversal to get sorted list
Find the target node in the list
Predecessor is the element before target
Successor is the element after target

java

import java.util.*;

class TreeNode {
    int val;
    TreeNode left, right;
    TreeNode(int x) { val = x; }
}

public class Solution {
    private void inorder(TreeNode root, List<TreeNode> nodes) {
        if (root == null) return;
        inorder(root.left, nodes);
        nodes.add(root);
        inorder(root.right, nodes);
    }
    
    public TreeNode[] findPredSuccBruteForce(TreeNode root, int key) {
        List<TreeNode> nodes = new ArrayList<>();
        inorder(root, nodes);
        
        TreeNode predecessor = null;
        TreeNode successor = null;
        
        for (int i = 0; i < nodes.size(); i++) {
            if (nodes.get(i).val == key) {
                if (i > 0) predecessor = nodes.get(i - 1);
                if (i < nodes.size() - 1) successor = nodes.get(i + 1);
                break;
            }
        }
        
        return new TreeNode[]{predecessor, successor};
    }
}

Complexity Analysis

Time Complexity: O(n) - Complete traversal
Space Complexity: O(n) - Storing all nodes

Approach 2: Optimal (Using BST Property)

Intuition

Use BST property to find predecessor and successor without complete traversal:

Successor: If node has right subtree, it's the leftmost node in right subtree. Otherwise, it's the nearest ancestor for which the node is in left subtree.
Predecessor: If node has left subtree, it's the rightmost node in left subtree. Otherwise, it's the nearest ancestor for which the node is in right subtree.

Algorithm

Search for the key while updating predecessor/successor
When going right, current node is a potential predecessor
When going left, current node is a potential successor
If key found and has right child, successor is min in right subtree
If key found and has left child, predecessor is max in left subtree

java

class TreeNode {
    int val;
    TreeNode left, right;
    TreeNode(int x) { val = x; }
}

public class Solution {
    private TreeNode predecessor;
    private TreeNode successor;
    
    public void findPredecessorSuccessor(TreeNode root, int key) {
        predecessor = null;
        successor = null;
        
        // First, find the node
        TreeNode curr = root;
        while (curr != null) {
            if (key < curr.val) {
                successor = curr;  // Current could be successor
                curr = curr.left;
            } else if (key > curr.val) {
                predecessor = curr;  // Current could be predecessor
                curr = curr.right;
            } else {
                // Key found
                // Predecessor: Max in left subtree
                if (curr.left != null) {
                    TreeNode temp = curr.left;
                    while (temp.right != null) {
                        temp = temp.right;
                    }
                    predecessor = temp;
                }
                
                // Successor: Min in right subtree
                if (curr.right != null) {
                    TreeNode temp = curr.right;
                    while (temp.left != null) {
                        temp = temp.left;
                    }
                    successor = temp;
                }
                break;
            }
        }
    }
    
    public TreeNode getPredecessor() { return predecessor; }
    public TreeNode getSuccessor() { return successor; }
}

Complexity Analysis

Time Complexity: O(h) where h is height
Space Complexity: O(1) - Only using pointers

Approach 3: Finding Only Successor (LeetCode Style)

Intuition

For finding just the inorder successor, we can simplify the logic.

Algorithm

If node has right subtree, successor is leftmost in right subtree
Otherwise, traverse from root tracking the last node where we went left

java

class TreeNode {
    int val;
    TreeNode left, right;
    TreeNode(int x) { val = x; }
}

public class Solution {
    public TreeNode inorderSuccessor(TreeNode root, TreeNode p) {
        TreeNode successor = null;
        
        while (root != null) {
            if (p.val >= root.val) {
                root = root.right;
            } else {
                successor = root;
                root = root.left;
            }
        }
        
        return successor;
    }
    
    public TreeNode inorderPredecessor(TreeNode root, TreeNode p) {
        TreeNode predecessor = null;
        
        while (root != null) {
            if (p.val <= root.val) {
                root = root.left;
            } else {
                predecessor = root;
                root = root.right;
            }
        }
        
        return predecessor;
    }
}

Complexity Analysis

Time Complexity: O(h) where h is height
Space Complexity: O(1)

Key Takeaways

Inorder gives sorted order: Predecessor and successor are adjacent in sorted sequence
BST property helps: We don't need full traversal
Two cases: Node has children vs node doesn't have children
Successor: Min in right subtree OR nearest ancestor with node in left subtree
Predecessor: Max in left subtree OR nearest ancestor with node in right subtree
This is LeetCode #285 (Inorder Successor) and #510
Essential for BST deletion (finding replacement node)

Find inorder successor and inorder predecessor in a BST

Problem Statement

Approach 1: Brute Force (Inorder Traversal)

Intuition

Algorithm

Complexity Analysis

Approach 2: Optimal (Using BST Property)

Intuition

Algorithm

Complexity Analysis

Approach 3: Finding Only Successor (LeetCode Style)

Intuition

Algorithm

Complexity Analysis

Key Takeaways