[CC150][4.6] Write an algorithm to find the ‘next’ node (i e , in-order successor) of a given node in a binary search tree where each node has a link to its parent.

findNextNode.java

// if current node has right subtree, return most left node of the right child.
// else trace back to its parent, if the parent is smaller than current node, then consider parent's parent...
// until parent node is bigger than current node.
public class findNextNode<Key extends Comparable<Key>> {
	private Node root;
	
	private class Node {
		private Key key;
		private Node left, right;
		private Node parent;
		
		public Node(Key key, Node parent) {
			this.key = key;
			this.parent = parent;
		}
	}
	public findNextNode(Key[] keys) {
		for (Key key : keys)
			root = put(root, key, null);
	}
	
	public Key findNext(Key key) {
		Node curr = find(root, key);
		Node next;
		if (curr.right != null) {
			next = curr.right;
			while (next.left != null)
				next = next.left;
		}
		else {
			next = curr.parent;
			while (next.key.compareTo(key) < 0)
				next = next.parent;
		}
		return next.key;
	} 
	
	private Node find(Node x, Key key) {
		if (x == null)
			return null;
		int cmp = key.compareTo(x.key);
		if (cmp < 0) return find(x.left, key);
		else if (cmp > 0) return find(x.right, key);
		else return x;
	}
	
	private Node put(Node x, Key key, Node parent) {
		if (x == null)
			return new Node(key, parent);
		int cmp = key.compareTo(x.key);
		if (cmp < 0) x.left = put(x.left, key, x);
		if (cmp > 0) x.right = put(x.right, key, x);
		return x;
	}
	
	public static void main(String[] args) {
		int N = 20;
		Integer[] data = new Integer[N];
		for (int i = 0; i < N; i++) data[i] = i;
		findNextNode<Integer> test = new findNextNode<Integer>(data);
		for (int i = 0; i < N - 1; i++)
			System.out.println("next to " + i + ": " + test.findNext(i));
	}
}