CareerCup

This program is fortunately working, though I spent a few hours writing it. To add readability to the code, I have added some comments.

The tricky part is when you want to delete a node which has two children (right and left) without having a child which has the same value as the current node has. First find the successor, then swap the node with its successor and after that delete the node ( which you are sure it has at most one child).

public class Tree {
	private Node root;
	
	public void insert(int x){
		Node n = new Node(x);
		this.insert(n);
	}
	public void insert(Node n){
		if(root == null){
			root = n;
			return;
		}else{
			this.insert(root,n);
		}
	}
	private void insert(Node curRoot, Node n){
		if(curRoot.value == n.value){
			Node temp = curRoot;
			while(temp.below!= null){
				temp = temp.below;
			}
			temp.below = n;
			n.parent = temp;
			return;
		}
		
		if(curRoot.value > n.value){
			if(curRoot.left != null){
				insert(curRoot.left,n);
				return;
			}else{
				curRoot.left = n;
				n.parent = curRoot;
				return;
			}
		}else{ // curRoot.value < n.value
			if(curRoot.right != null){
				insert(curRoot.right,n);
				return;
			}else{
				curRoot.right = n;
				n.parent = curRoot;
				return;
			}
		}
	}
	
	public void printRoot(){
		if(root != null)
			System.out.println("Root value: "+root.value);
		else
			System.err.println("Root is null.");
	}
	public void print(){
		if(root == null){
			System.out.println("No tree!");
		}
		else{
			print(root);
		}
	}
	private void print(Node n){
		if(n.left!= null){
			print(n.left);
		}
		
		//current node and all nodes with the equal value
		System.out.println(n.value);
		if(n.below != null){
			print(n.below);
		}
		
		if(n.right != null){
			print(n.right);
		}
	}
	// get the min Node in the subtree of cur (includes cur)
	// if two values are the least, it returns the parent!
	public Node getMin(Node cur){
		Node temp = cur;
		while(temp.left != null){
			temp = temp.left;
		}
		return temp;
	}
	
	// if there is a node with the same value below current node, that is the successor.
	// if there is a right child for current node, run the getMin() on the right node.
	// if there is not a right child, while this child is in the right side of its parent go upward. If you reach the situation that the parent's
	// left child is current node, return it. otherwise return null.
	public Node successor(Node cur){
		if(cur == null){
			System.err.println("Node is null in successor funtion!");
			return null;
		}
		
		if(cur.below != null){
			return cur.below;
		}
		
		if(cur.right != null){
			return getMin(cur.right);
		}else{
			Node temp = cur;
			while(temp.parent != null && temp.parent.right == temp){
				temp = temp.parent;
			}
			if(temp.parent == null){
				return null;
			}else{
				return temp.parent;
			}
		}
		
	}
	
	public void delete(Node n){
		System.out.println("I am gonna delete " + n.value);
		if(n.below != null){
			deleteIfBelowIsNotNull(n);
			return;
		}
		if(n.right == null && n.left == null){
			
			if(n.parent != null){
				if(n.parent.right == n)
					n.parent.right = null;
				else if(n.parent.left == n)
					n.parent.left = null;
				else if(n.parent.below == n)
					n.parent.below = null;
			}else{
				root = null;
			}
			n = null;
			return;
		}
		if(n.right == null || n.left == null){
			deleteWithOneChild(n);
			return;
		}
		
		if(n.right != null && n.left != null){
			deleteWithTwoChildren(n);
		}
		
	}
	private void deleteIfBelowIsNotNull(Node n){
		n.below.parent = n.parent;
		n.below.right = n.right;
		n.below.left = n.left;
		if(n.parent == null){ // n == root!
			root = n.below;
			n = null;
			return;
		}else if(n.parent.right == n){
			n.parent.right = n.below;
			n = null;
			return;
		}else if(n.parent.below == n){
			n.parent.below = n.below;
			n=null;
			return;
		}else if(n.parent.left== n){
			n.parent.left = n.below;
			n = null;
			return;
		}
		System.err.println("An error occured in deleteIfBelowIsNotNull");
		return;
	}
	

	private void deleteWithOneChild(Node n) {
		if(n.right == null){
			if(n.parent == null){ // n == root
				root = n.left;
				n.left.parent = null;
				n = null;
				return;
			}
			else if(n == n.parent.right){
				n.parent.right = n.left;
				n.left.parent = n.parent;
				n = null;
				return;
			}else if(n == n.parent.left){
				n.parent.left = n.left;
				n.left.parent = n.parent;
				n = null;
				return;
			}else if(n == n.parent.below){
				System.err.println("There has to be something wrong in deleteWithOneChild function.");
				return;
			}
		}
		
		if(n.left == null){
			if(n.parent == null){ // n == root
				root = n.right;
				n.right.parent = null;
				n = null;
				return;
			}else if(n == n.parent.right){
				n.parent.right = n.right;
				n.right.parent = n.parent;
				n = null;
				return;
			}else if(n == n.parent.left){
				n.parent.left = n.right;
				n.right.parent = n.parent;
				n = null;
				return;
			}else if(n == n.parent.below){
				System.err.println("There has to be something wring in deleteWithOneChild function.(2)");
				return;
			}
		}
		
		System.err.println("There has to be something wring in deleteWithOneChild function.(3)");
		return;
	}
	//swap the node with its successor. successor is the minimum in the right children since we are sure that 
	// there is a child on right and also there is no node below current node. 
	//After the swap, delete n since we know it has at most one child.
	private void deleteWithTwoChildren(Node n) {
		
		Node successor = this.successor(n);
		
		//Copy all tree relationship of successor into temp variable.
		Node temp = new Node(successor.value);
		temp.parent = successor.parent;
		boolean isTempLeftChild = false;
		if(successor.parent.right == successor){
			successor.parent.right = temp;
		}else{
			successor.parent.left = temp;
			isTempLeftChild = true;
		}
		temp.right = successor.right;
		temp.left = successor.left;
		
		//Replace n with its successor
		successor.parent = n.parent;
		if(n.parent == null){
			successor.parent = null;
			root = successor;
		}else if(n.parent.left == n){
			n.parent.left = successor;
		}else{
			n.parent.right = successor;
		}
		successor.right = n.right;
		if(successor.right != null)
			successor.right.parent = successor;
		successor.left = n.left;
		if(successor.left != null)
			successor.left.parent = successor;
		
		
		
		// if successor was a direct child of n, set n's parent to successor. Otherwise n's parent is former successor's parent.
		if(temp.parent != n){
			n.parent = temp.parent;
		}else{
			n.parent = successor;
		}
		n.left = temp.left;
		n.right = temp.right;
		
		// If successor was the left child of its parent, set the left child of its parent to n.
		if(isTempLeftChild == true){
			if(temp.parent != n){
				temp.parent.left = n;
			}else{// when successor is the immediate child of n.
				successor.left = n;
			}
		// If successor was the right child of its parent, set the right child of its parent to n.	
		}else{
			if(temp.parent != n){
				temp.parent.right = n;
			}else{// when successor is the immediate child of n.
				successor.right = n;
			}
		}
		temp = null;
		
		// Now n and its successor are completely swapped. Time to delete n since we are sure that n does not have a child in its below
		// and we are sure that n will have no child or only one child.
		if(n.left == null && n.right == null){
			if(n.parent.left == n){
				n.parent.left = null;
			}else{
				n.parent.right = null;
			}
			n = null;
			return;
		}else{ // n has at most one child (on its right)
			
			deleteWithOneChild(n);
		}
		
	}

	
	
	public static void main(String[] args) {
		Tree t = new Tree();
		Node node = t.new Node(1);
		Node node2 = t.new Node(3);
		Node node3 = t.new Node(2);
		Node node4 = t.new Node(4);
		Node node5 = t.new Node(5);
		Node node6 = t.new Node(0);
		Node node7 = t.new Node(-1);
		Node node8 = t.new Node(1);
		Node node9 = t.new Node(1);
		
		t.print();
		t.insert(node);
		t.insert(node2);
		t.insert(node3);
		t.insert(node4);
		t.insert(node5);
		t.insert(node6);
		t.insert(node7);
		t.insert(node8);
		t.insert(node9);
		
		t.delete(node8);
		t.delete(node);
		t.delete(node9);
		
		t.print();
		t.printRoot();
		
	}
	
	
	
	public class Node {
		Node left;
		Node right;
		Node below;
		Node parent;
		int value;
		public Node(){
			this(Integer.MAX_VALUE);
			
		}
		public Node(int x){
			left = null;
			right = null;
			parent = null;
			value = x;
			
		}
	}
}

Node insert(Node root,int x)
{
	if(root==null)
{
	
	Node temp=new Node();
	temp.info=x;
	if(this.root==null)
	this.root=temp;
	return temp;
}
else if(root.info<x)
{
	root.right=insert(root.right,x);
}
else if(root.info>x)
{
	root.left=insert(root.left,x);

}
else
	root.equal=insert(root.equal,x);
return root;
}

1.Build the tree recursively.
2.go through all the ancestors .
3.And make the connections while the stack is getting empty.