Given a binary tree, write a method to find the nearest neighbor to the right of a given node.

FindRightNeighbor.java

public class FindRightNeighbor {
	
	Node root = null;
	
	public void insert(Node node) {
		if (root == null) {
			root = node;
			return;
		}
		
		Node current = root;
		while (true) {
			int compare = node.compareTo(current);
			if (compare < 0) {
				if (current.getLeftChild() != null) {
					current = current.getLeftChild();
				} else {
					current.setLeftChild(node);
					node.setParent(current);
					return;
				}
			} else if (compare > 0) {
				if (current.getRightChild() != null) {
					current = current.getRightChild();
				} else {
					current.setRightChild(node);
					node.setParent(current);
					return;
				}
			} else {
				//ignore duplicates
				return;
			}
		}
	}
	
	public Node findNeighborToTheRight(Node start) {
		if (start == null || start.getParent() == null) {
			return null;
		}
		
		int level = 0;
		Node current = start;
		Node parent = current.getParent();
		
		while (current.compareTo(parent) > 0) {
			parent = parent.getParent();
			level--;
			if (parent == null) {
				return null;
			}
		}
		
		Node child = parent.getRightChild();
		while (level < 0) {
			if (child.getLeftChild() != null) {
				child = child.getLeftChild();
				level++;
			} else if (child.getRightChild() != null) {
				child = child.getRightChild();
				level++;
			} else {
				return null;
			}
		}
		
		return child;
	}

	public static class Node {
		private int value;
		private Node parent;
		private Node leftChild;
		private Node rightChild;
		
		public Node(int value) {
			this.value = value;
		}
		
		public Node(int value, Node parent) {
			this.value = value;
			this.parent = parent;
		}
		
		public int getValue() {
			return value;
		}
		
		public Node getParent() {
			return parent;
		}
		
		public void setLeftChild(Node node) {
			leftChild = node;
		}
		
		public void setRightChild(Node node) {
			rightChild = node;
		}
		
		public void setParent(Node parent) {
			this.parent = parent;
		}
		
		public Node getLeftChild() {
			return leftChild;
		}
		
		public Node getRightChild() {
			return rightChild;
		}
		
		public int compareTo(Node node) {
			return value - node.getValue();
		}
		
		@Override
		public String toString() {
			return new Integer(value).toString();
		}
	}
	
	public static void main(String args[]) {
		FindRightNeighbor tree = new FindRightNeighbor();
		Node[] nodes = new Node[21];
		for (int i = 0; i < nodes.length; i++) {
			nodes[i] = new Node(i);
		}
		
		tree.insert(nodes[10]);
		tree.insert(nodes[5]);
		tree.insert(nodes[3]);
		tree.insert(nodes[4]);
		tree.insert(nodes[1]);
		tree.insert(nodes[2]);
		tree.insert(nodes[0]);
		tree.insert(nodes[7]);
		tree.insert(nodes[8]);
		tree.insert(nodes[9]);
		tree.insert(nodes[6]);
		tree.insert(nodes[15]);
		tree.insert(nodes[12]);
		tree.insert(nodes[11]);
		tree.insert(nodes[13]);
		tree.insert(nodes[14]);
		tree.insert(nodes[18]);
		tree.insert(nodes[16]);
		tree.insert(nodes[17]);
		tree.insert(nodes[20]);
		tree.insert(nodes[19]);
		
//		                 10
//		                /  \
//                            /      \
//                          /          \
//                        /              \
//		         5                15
//		        / \              /  \
//		      /     \          /      \
//		     3       7        12       18
//		    / \     / \      /  \     /  \
//		   1   4   6   8   11    13  16   20
//		  / \           \         \   \   /
//		 0   2           9        14  17 19
		
		for (int i = 0; i < nodes.length; i++) {
			System.out.println("Node to the right of " + i + " is: " + 
					tree.findNeighborToTheRight(nodes[i]));
		}
	}
	
}