InOrderSuccessor.java

package trees;

import java.util.ArrayList;
import java.util.List;

public class InOrderSuccessor {

    /*
     * Inorder successor of a node in binary Search Tree (BST) is the next node in inorder traversal.
     * Write a method to find inorder successor of a given value "d" in a BST.
     * Binary Node: 100, 50, 200, 25, 75, 125, 350
     *
     * Inorder successor of 25 is 50
     * Inorder successor of 50 is 75
     * Inorder successor of 75 is 100
     * Inorder successor of 100 is 125
     * Inorder successor of 125 is 200
     * Inorder successor of 200 is 350
     * Inorder successor of 350 is NULL since it is the last node
     *
     * Runtime Complexity:
     * Logarithmic, O(logn)
     *
     * Memory Complexity:
     * Constant, O(1).
     *
     * Find the value d in BST. If d has a right child then the left most child in right child's subtree
     * will be the in-order successor of d. This would also be the child with the minimum value in that subtree.
     * Find the value d in BST. If d has no right child then:
     * in-order successor is NULL if d is right most node in the BST i.e. last node in the in-order traversal
     * in-order successor is the node with minimum value higher than d in the parent chain of d
     *
     * */

    private static class Node {
        private int data;
        private Node left, right;

        Node(int item) {
            data = item;
            left = right = null;
        }

        public int getData() {
            return data;
        }

        public Node getLeft() {
            return left;
        }

        public Node getRight() {
            return right;
        }
    }


    private Node root1;

    private static Node findMin(Node root) {
        if (root == null) return null;

        while (root.left != null) {
            root = root.left;
        }

        return root;
    }

    protected static Node inOrderSuccessorBst(Node root,
                                              int d) {

        if (root == null) {
            return null;
        }

        Node successor = null;

        while (root != null) {

            if (root.data < d) {
                root = root.right;
            } else if (root.data > d) {
                successor = root;
                root = root.left;
            } else {
                if (root.right != null) {
                    successor = findMin(root.right);
                }
                break;
            }
        }
        return successor;
    }


    protected List<Integer> values = new ArrayList<>();
    protected List<Integer> storeKeyValues(Node root) {
        treeTravel(root);
        return values;
    }

    private void treeTravel(Node node) {
        if (node != null) {
            treeTravel(node.left);
            values.add(node.data);
            treeTravel(node.right);
        }
    }


    public static void main(String[] args) {
        ArrayList<Integer> orig_data = new ArrayList<>();
        orig_data.add(25);
        orig_data.add(125);
        orig_data.add(200);
        orig_data.add(350);
        orig_data.add(50);
        orig_data.add(75);
        orig_data.add(100);

        InOrderSuccessor inOrderSuccessor = new InOrderSuccessor();
        inOrderSuccessor.root1 = new Node(100);
        inOrderSuccessor.root1.left = new Node(50);
        inOrderSuccessor.root1.right = new Node(200);
        inOrderSuccessor.root1.left.left = new Node(25);
        inOrderSuccessor.root1.left.right = new Node(75);
        inOrderSuccessor.root1.right.left = new Node(125);
        inOrderSuccessor.root1.right.right = new Node(350);


        List<Integer> bstToList = inOrderSuccessor.storeKeyValues(inOrderSuccessor.root1);

        for (Integer d : orig_data) {
            Node successor = inOrderSuccessorBst(inOrderSuccessor.root1, d);

            int i = bstToList.indexOf(d);
            Integer expected_val = null;

            if (i < bstToList.size() - 1) {
                expected_val = bstToList.get(i + 1);
            }

            if (successor != null) {
                if (expected_val.intValue() != successor.data) {
                    System.out.println("*******" + d + " ==== " + expected_val + ", " + successor.data + "*****");
                }
            }

            if (successor != null) {
                System.out.print("(" + d + ", " + successor.data + ") ");

            } else {
                System.out.print("(" + d + ", null) ");
            }
        }
    }
}