BST Inorder Predecessor in DSA Java - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Find the inorder predecessor value in a BST

What is the output of the following Java code that finds the inorder predecessor of a node with value 15 in the BST?

DSA Java

class Node {
    int val;
    Node left, right;
    Node(int v) { val = v; left = right = null; }
}

public class BSTPredecessor {
    static Node root;

    static Node inorderPredecessor(Node root, int key) {
        Node predecessor = null;
        Node current = root;
        while (current != null) {
            if (key <= current.val) {
                current = current.left;
            } else {
                predecessor = current;
                current = current.right;
            }
        }
        return predecessor;
    }

    public static void main(String[] args) {
        root = new Node(20);
        root.left = new Node(10);
        root.right = new Node(30);
        root.left.left = new Node(5);
        root.left.right = new Node(15);
        root.right.left = new Node(25);
        root.right.right = new Node(35);

        Node pred = inorderPredecessor(root, 15);
        System.out.println(pred != null ? pred.val : "null");
    }
}

A null

B 5

C 10

D 15

💡 Hint

Remember, inorder predecessor is the largest value smaller than the given key.

The inorder predecessor of 15 is the largest node smaller than 15. In the BST, 10 is the largest value less than 15, so the output is 10.

❓ Predict Output

intermediate

Output when node has left subtree

What will be printed by this Java code that finds the inorder predecessor of node 20 in the BST?

DSA Java

class Node {
    int val;
    Node left, right;
    Node(int v) { val = v; left = right = null; }
}

public class BSTPredecessor {
    static Node root;

    static Node findMax(Node node) {
        while (node.right != null) {
            node = node.right;
        }
        return node;
    }

    static Node inorderPredecessor(Node root, int key) {
        Node current = root;
        while (current != null && current.val != key) {
            if (key < current.val) {
                current = current.left;
            } else {
                current = current.right;
            }
        }
        if (current == null) return null;

        if (current.left != null) {
            return findMax(current.left);
        }

        Node predecessor = null;
        Node ancestor = root;
        while (ancestor != current) {
            if (current.val > ancestor.val) {
                predecessor = ancestor;
                ancestor = ancestor.right;
            } else {
                ancestor = ancestor.left;
            }
        }
        return predecessor;
    }

    public static void main(String[] args) {
        root = new Node(20);
        root.left = new Node(10);
        root.right = new Node(30);
        root.left.left = new Node(5);
        root.left.right = new Node(15);
        root.right.left = new Node(25);
        root.right.right = new Node(35);

        Node pred = inorderPredecessor(root, 20);
        System.out.println(pred != null ? pred.val : "null");
    }
}

A null

B 10

C 25

D 15

💡 Hint

If the node has a left subtree, the predecessor is the max in that subtree.

Node 20 has a left child 10, which has a right child 15. The max in left subtree is 15, so the inorder predecessor is 15.

🔧 Debug

advanced

Identify the error in inorder predecessor code

What error will this Java code produce when trying to find the inorder predecessor of 10?

DSA Java

class Node {
    int val;
    Node left, right;
    Node(int v) { val = v; left = right = null; }
}

public class BSTPredecessor {
    static Node root;

    static Node inorderPredecessor(Node root, int key) {
        Node predecessor = null;
        Node current = root;
        while (current != null) {
            if (key < current.val) {
                current = current.left;
            } else if (key > current.val) {
                predecessor = current;
                current = current.right;
            } else {
                if (current.left != null) {
                    Node temp = current.left;
                    while (temp.right != null) {
                        temp = temp.right;
                    }
                    return temp;
                }
                break;
            }
        }
        return predecessor;
    }

    public static void main(String[] args) {
        root = new Node(20);
        root.left = new Node(10);
        root.right = new Node(30);
        root.left.left = new Node(5);
        root.left.right = new Node(15);

        Node pred = inorderPredecessor(root, 10);
        System.out.println(pred != null ? pred.val : "null");
    }
}

A Prints 5

B NullPointerException

C Prints 15

D Prints null

💡 Hint

Check the left subtree of node 10 for predecessor.

Node 10 has left child 5 and right child 15. The inorder predecessor is the max in left subtree, which is 5. No error occurs.

❓ Predict Output

advanced

Output when node has no left subtree

What will be the output of this Java code that finds the inorder predecessor of node 25 in the BST?

DSA Java

class Node {
    int val;
    Node left, right;
    Node(int v) { val = v; left = right = null; }
}

public class BSTPredecessor {
    static Node root;

    static Node inorderPredecessor(Node root, int key) {
        Node current = root;
        Node predecessor = null;
        while (current != null) {
            if (key <= current.val) {
                current = current.left;
            } else {
                predecessor = current;
                current = current.right;
            }
        }
        return predecessor;
    }

    public static void main(String[] args) {
        root = new Node(20);
        root.left = new Node(10);
        root.right = new Node(30);
        root.left.left = new Node(5);
        root.left.right = new Node(15);
        root.right.left = new Node(25);
        root.right.right = new Node(35);

        Node pred = inorderPredecessor(root, 25);
        System.out.println(pred != null ? pred.val : "null");
    }
}

A 15

B 20

C 25

D null

💡 Hint

When no left subtree, predecessor is the last node smaller than key on path.

Node 25 has no left child. The last node smaller than 25 on path is 20, so predecessor is 20.

🧠 Conceptual

expert

Understanding inorder predecessor in BST

Which statement correctly describes the inorder predecessor of a node in a BST?

A It is the rightmost node in the left subtree of the given node if the left subtree exists.

B It is the node with the smallest value greater than the given node.

C It is always the parent node of the given node.

D It is the leftmost node in the right subtree of the given node.

💡 Hint

Think about inorder traversal order and where predecessor lies.

The inorder predecessor is the largest node smaller than the given node. If left subtree exists, it is the rightmost node there.

Practice

1. What is the inorder predecessor of a node in a Binary Search Tree (BST)?

easy

A. The node with the largest value smaller than the given node

B. The node with the smallest value larger than the given node

C. The left child of the given node

D. The right child of the given node

Solution

1. Step 1: Understand inorder traversal order

   Inorder traversal visits nodes in ascending order for BST, so predecessor is the previous node in this order.

2. Step 2: Define inorder predecessor

   The inorder predecessor is the node with the largest value smaller than the current node's value.

3. Final Answer:

   The node with the largest value smaller than the given node -> Option A

4. Quick Check:

   Inorder predecessor = largest smaller value [OK]

Hint: Predecessor is just before current node in sorted order [OK]

Common Mistakes:

• Confusing predecessor with successor
• Thinking predecessor is always left child
• Assuming predecessor is the parent node

2. Which of the following Java method signatures correctly represents a function to find the inorder predecessor in a BST node?

easy

A. public Node findInorderSuccessor(Node root, int key)

B. public int findInorderPredecessor(int[] arr, int key)

C. public Node findInorderPredecessor(Node root, int key)

D. public void findInorderPredecessor(Node root)

Solution

1. Step 1: Identify correct parameters for BST predecessor method

   We need the BST root and the key node value to find predecessor, so method should accept Node root and int key.

2. Step 2: Check method return type and name

   Return type should be Node (the predecessor node), and method name should indicate predecessor, so 'findInorderPredecessor(Node root, int key)' fits.

3. Final Answer:

   public Node findInorderPredecessor(Node root, int key) -> Option C

4. Quick Check:

   Correct signature includes root, key, returns Node [OK]

Hint: Method needs root and key, returns Node predecessor [OK]

Common Mistakes:

• Using array instead of BST Node
• Confusing predecessor with successor method name
• Wrong return type like void or int

3. Given the BST below and the code snippet, what will be the output?

    20
   /  \
 10   30
   
Node predecessor = findInorderPredecessor(root, 20);
System.out.println(predecessor != null ? predecessor.data : "null");

Assuming findInorderPredecessor is correctly implemented.

medium

A. null

B. 10

C. 30

D. 20

Solution

1. Step 1: Identify inorder predecessor of node 20 in BST

   Inorder predecessor is the largest node smaller than 20. Left subtree of 20 has node 10, which is smaller and largest in left subtree.

2. Step 2: Confirm output of print statement

   Predecessor node data is 10, so printed output is "10".

3. Final Answer:

   10 -> Option B

4. Quick Check:

   Largest smaller node than 20 is 10 [OK]

Hint: Predecessor is max in left subtree if left exists [OK]

Common Mistakes:

• Printing null when left subtree exists
• Confusing successor with predecessor
• Printing the node itself instead of predecessor

4. Consider this buggy Java method to find the inorder predecessor in a BST:

public Node findInorderPredecessor(Node root, int key) {
    Node predecessor = null;
    while (root != null) {
        if (key < root.data) {
            root = root.left;
        } else {
            predecessor = root;
            root = root.right;
        }
    }
    return predecessor;
}

What is the main issue with this code?

medium

A. It does not handle the case when the node has a left subtree

B. It incorrectly updates predecessor when key equals root.data

C. It causes infinite loop for some inputs

D. It returns the successor instead of predecessor

Solution

1. Step 1: Analyze traversal logic for predecessor

   The code moves left if key < root.data, else moves right and updates predecessor. But it never checks left subtree of the node itself.

2. Step 2: Identify missing left subtree handling

   If the node has a left subtree, the predecessor is the maximum node in that left subtree, which this code does not check.

3. Final Answer:

   It does not handle the case when the node has a left subtree -> Option A

4. Quick Check:

   Missing left subtree max check causes wrong predecessor [OK]

Hint: Check left subtree max for predecessor if it exists [OK]

Common Mistakes:

• Ignoring left subtree max node
• Confusing predecessor with successor logic
• Assuming predecessor is always ancestor

5. You have a BST and want to find the inorder predecessor of a node with value 15. The node has no left child. Which approach correctly finds the predecessor?

hard

A. Find the maximum node in the left subtree of 15

B. Return the right child of node 15

C. Return null because no left child exists

D. Traverse from root, keep track of last node with value less than 15

Solution

1. Step 1: Understand predecessor when no left child

   If node has no left child, predecessor is one of its ancestors with value less than node's value.

2. Step 2: Use traversal from root to track predecessor

   Traverse from root to node 15, keep updating predecessor to last node with value less than 15.

3. Final Answer:

   Traverse from root, keep track of last node with value less than 15 -> Option D

4. Quick Check:

   No left child means ancestor with smaller value is predecessor [OK]

Hint: Track last smaller ancestor when no left child [OK]

Common Mistakes:

• Returning null immediately if no left child
• Trying to find max in non-existent left subtree
• Returning right child mistakenly