Question4_6.java

/**
 * Write an algorithm to find the 'next' node (i.e., in-order successor) of a given node in a binary search tree.
 * You may assume that each node has a link to its parent.
 * 
 * Time  Complexity: O(h)
 * Space Complexity: O(1)
 */

public class Question4_6 {
    public TreeNode getSuccessor(TreeNode node) {
        if (node == null) {
            return null;
        }
        
        if (node.right != null) {
            TreeNode retNode = node.right;
            while (retNode.left != null) {
                retNode = retNode.left;
            }
            return retNode;
        }
        
        TreeNode prevNode = node; 
        TreeNode retNode = node.parent;
        while (retNode != null && retNode.right == prevNode){
            prevNode = retNode;
            retNode = retNode.parent;
        }
        
        return retNode;
    }
    
    
    public static void main(String[] args) {
        Question4_6 question4_6 = new Question4_6();
        TreeNode root = new TreeNode(4, null);
        root.left = new TreeNode(2, root);
        root.right = new TreeNode(6, root);
        root.left.left = new TreeNode(1, root.left);
        root.left.right = new TreeNode(3, root.left);
        root.right.left = new TreeNode(5, root.right);
        root.right.right = new TreeNode(7, root.right);

        
        System.out.println(question4_6.getSuccessor(root.left.left).value);
        System.out.println(question4_6.getSuccessor(root.left).value);
        System.out.println(question4_6.getSuccessor(root.left.right).value);
        System.out.println(question4_6.getSuccessor(root).value);
        System.out.println(question4_6.getSuccessor(root.right.left).value);
        System.out.println(question4_6.getSuccessor(root.right).value);
        System.out.println(question4_6.getSuccessor(root.right.right) == null ? "null" : "not null");
    }
}


class TreeNode {
    int value;
    TreeNode left;
    TreeNode right;
    TreeNode parent;
    
    public TreeNode() {
        this(0, null, null, null);
    }
    
    public TreeNode(int value, TreeNode parent) {
        this(value, null, null, parent);
    }
    
    public TreeNode(int value, TreeNode left, TreeNode right, TreeNode parent) {
        this.value = value;
        this.left = left;
        this.right = right;
        this.parent = parent;
    }
}