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.

CC150-4.6.java

package POJ;

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

public class Main{
 
	/**
	 * 
	 *  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.
	 *  
	 *  Solution:
	 *  1. if the node has a right child, return the leftmost node of its right subtree
	 *  2. else if the node is the left child of its parent, return its parent
	 *  3. else (the node is the right child of its parent) then keep searching upwards the tree until the situation of (2) is found
	 *  
	 *  @Runtime & spaces
	 * 	runtime: O(H)
	 * 	space: O(1)
	 * 
	 */
	public static void main(String[] args) {
		Main so=new Main();
	/*	_______7______
	       /              \
	    __10__          ___2
	   /      \        /
	   4       3      _8
	            \    /
	             1  11 		*/
		tempNode root = new tempNode(7,null);
        root.left = new tempNode(10,root);
        root.right = new tempNode(2,root);
        root.left.left = new tempNode(4,root.left);
        root.left.right = new tempNode(3,root.left);
        root.left.right.right = new tempNode(1,root.left.right);
        root.right.left = new tempNode(8,root.right);
        root.right.left.left = new tempNode(11,root.right.left);
        
        System.out.println(so.getSuccessor(root.left.left).val);
        System.out.println(so.getSuccessor(root.left).val);
        System.out.println(so.getSuccessor(root.left.right).val);
        System.out.println(so.getSuccessor(root).val);
        System.out.println(so.getSuccessor(root.right.left).val);
        System.out.println(so.getSuccessor(root.right).val);
	}
	public tempNode getSuccessor(tempNode node){
		if(node==null)
			return null;
		// node has a right child
		if(node.right!=null)
			return getLeftMost(node.right);
		// node has no right child and is the left child of its parent.
        // Note that actually we do not need this line here 
        // since it is covered by the part below.
        // but since this is how we thought through the problem, it makes the process clearer.
		if(node==node.parent.left)
			return node.parent;
		// target has no right child and is its parent's right child
		while(node==node.parent.right)
			node=node.parent;
		return node.parent;
	}
	private tempNode getLeftMost(tempNode node) {
		// TODO Auto-generated method stub
		while(node.left!=null)
			node=node.left;
		return node;
	}
}
class tempNode{
	int val;
	tempNode left;
	tempNode right;
	tempNode parent;
	
	public tempNode(){
		this(0,null,null,null);
	}
	
	public tempNode(int value,tempNode parent){
		this(value,null,null,parent);
	}
	
	public tempNode(int value, tempNode left, tempNode right, tempNode parent) {
		// TODO Auto-generated constructor stub
		this.val=value;
		this.left=left;
		this.right=right;
		this.parent=parent;
	}
}