CTCI 4.6

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.

CTCI 4.6-1.java

//in-order

public static Node findNextInOrderNodeBST(Node root){
    if(root == null) return null;
    
    if(root.right != null){
        Node firstLeft = root.right;
        while(firstLeft.left != null){
            firstLeft = firstLeft.left;
        }
        return firstLeft;
    }
    
    else{
        Node thisParent = root.thisParent;
        while(thisParent != null && thisParent.value < root.value){
            thisParent = thisParent.parent;
        }
        return thisParent;
    }
}

CTCI 4.6-2.java

//pre-order

public static Node findNextPreOrderNodeBST(Node root){
    if(root == null) return null;
    
    if(root.left != null) return root.left;
    else if(root.right != null) return root.right;
    else{
        Node thisParent = root.parent;
        while(thisParent != null && (thisParent.value < root.value || thisParent.right == null)){
            thisParent = thisParent.parent;
        }        
        if(thisParent == null) return null;
        else return thisParent.right;
    }
}