CareerCup

public class DeleteAllNodesOnAPath {
    static class Node
    {
    	int data;
    	Node left;
    	Node right;
    	public Node( int data )
    	{
    		this.data = data;
    	}
    }
    
    public Node deleteNode(Node root, int sum)
    {
        deleteNodeRecursive(root, sum);
    	return root;
    }
    
    
	private boolean deleteNodeRecursive(Node root, int sum) {
	    if (root == null)
	    {
	    	return sum >=0 ? false : true;
	    }
	    sum = sum- root.data;
		boolean lValue = deleteNodeRecursive(root.left, sum);
		boolean rValue = deleteNodeRecursive(root.right, sum);
        boolean isLeftValid = true;
        boolean isRightValid = true;
		if (!lValue)
		{
			isLeftValid = false;
			root.left = null;
		}
		
		if (!rValue)
		{
			isRightValid = false;
			root.right = null;
		}
		if (!isLeftValid && !isRightValid)
		{
			return false;
		}
		else
		{
			return true;			
		}
	}
	/**
	 * @param args
	 */
	public static void main(String[] args) {
		
//		                       40
//	                         /    \ 
//	                       10      100    
//	                               /  \
//	                             60   150    
		
      Node root = new Node(40);
      root.left = new Node(10);
      root.right = new Node(100);
      root.right.right = new Node(150);
      root.right.left = new Node(60);

      root = new DeleteAllNodesOnAPath().deleteNode(root, 210);
	}

}

Node exploreAll (Node root, int sum, int val ) {//val is the threshold value set
	if (root == null)
		return root;

	Node LC = root.left;
	Node RC = root.right;

	if ( LC!= null ) 
		Node status1 = exploreAll (LC,sum+root.data,val);
	
	if ( RC != null ) 
		Node status2 = exploreAll (RC,sum+root.data,val); //can store root.data in a temporary variable to save one computation.//

	checkLeft (status1, root, RC, LC);
	checkRight (status2, root, LC, RC);

	if ( LC == null && RC == null ) {
		if ( sum + root.data < val ) {
			root = null;
			return root;
		}
	}

	return root;
}

void checkLeft (Node status1, Node root, Node RC, Node LC) {
	if ( root != null && status1 == null ) {
		if ( RC != null ) {
			if ( root.parent != null ) {
				if ( root.parent.left == root ) 
					root.parent.left = RC;
				else
					root.parent.right = RC;
			}
			else {
				Node newNode = new Node ();
				newNode.left = LC;
				newNode.right = RC;
			}
		}
	}
	root = null;
}

void checkRight (Node status2, Node root, Node LC, Node RC) {
	if ( root != null && status2 == null ) {
		if ( LC != null ) {
			if ( root.parent != null ) {
				if ( root.parent.left == root ) 
					root.parent.left = LC;
				else
					root.parent.right = LC;
			}
			else {
				Node newNode = new Node ();
				newNode.left = LC;
				newNode.right = RC;
			}
		}
	}
	root = null;
}