CareerCup

All the parent-child relations would remain same except those who are parents of that leaf node .i.e, the parent of the leaf node , its parent , and so on till the root . Their relationship will be reversed . The parent will become child and vice versa .
To get the modified tree , just reverse that one chain of leaf's parents . It can be done easily by swapping the leaf with the root , leaf parent with the root child and so on .
A diagram could explain more properly . Hope this helps .

Following a version that also maintains a nodes parent:

{
	public Node upsideDownTreeRercursive(Node node, Node newRoot) {
		Node oldParent = null;
		
		if (node == null)
			return null;
		
		if (node == newRoot) {
			node.setLeftChild(node.getParent());
			node.setParent(null);
			return node;
		}
		
		if (upsideDownTreeRercursive(node.getLeftChild(), newRoot) != null) {
			oldParent = node.getParent();
			node.setParent(node.getLeftChild());
			node.setLeftChild(oldParent);
			return node;
		}
		
		if (upsideDownTreeRercursive(node.getRightChild(), newRoot) != null) {
			oldParent = node.getParent();
			node.setParent(node.getRightChild());
			node.setRightChild(oldParent);
			return node;	
		}
		
		return null;
	}

CAn you be more specific as to what do you mean by falling down? An example would be great.

can you explain with Example means before and after result.

given tree.
......

1
              /  \
            2   3
           /  \    \ 
         4   5   6
let the leaf node be 5.
then it becomes something like 
                        5
                          \
                          2
                         /  \
                       1   4
                      /
                    3
                   /
                 6

#perl syntax
my $n=$designated_leaf;

my $ret=flip_tree($root,null,$left);
if($ret!=0){
        $ret=flip_tree($root,null,$right);
}

sub flip_tree{

        my ($r,$p,$side)=(shift,shift,shift);
        my $ret=0;
        if ($r==$n){
                $ret=1;
        }
        if($node_found==0){
                $ret=flip_tree($node->left, $r, $left);
        }
        if($node_found==0){
                $ret=flip_tree($node->right,$r, $right);
        }

        if($ret==1){
                #swap parent and $r

                if ($side==left){
                        $r->left=$p;

                }else{
                        $r->right=$p;
                }
        }
        return $ret;

}

#perl syntax 
my $n=$designated_leaf;

my $ret=flip_tree($root,null,$left);
if($ret!=0){
        $ret=flip_tree($root,null,$right);
}

sub flip_tree{

        my ($r,$p,$side)=(shift,shift,shift);
        my $ret=0;
        if($r==null) return 0;
        if ($r==$n){
                $ret=1;
        }
        if($ret==0){
                $ret=flip_tree($node->left, $r, $left);
        }

        if($ret==0){
                $ret=flip_tree($node->right,$r, $right);
        }

        if($ret==1){
                #swap parent and $r

                if ($side==left){
                        $r->left=$p;

                }else{
                        $r->right=$p;
                }
        }
        return $ret;

}

Node findNewRoot(Node root, Node newRoot)
{
	if(root != null && newRoot != null)
	{
		if(root.ele == newRoot.ele)
		{
			return root;
		}
		Node R ;
		if(rooot.ele < newRoot.ele)
		{
			R = findNewRoot(root.right, newRoot);
			root.right = null;		
		}
		else
		{
			R = findNewRoot(root.left, newRoot)
			root.left = null;
		}
		R.insert(root);
		return R;
	}
	return null;
}

Start from the root, search only the left branch, for each node in that search, change the left child of that node to the parent, the right child to be the left child.

create a graph and do bfs traversal thus getting predecessor array

create a graph and do bfs traversal thus getting predecessor array

Node* flipWrapper(Node* root, Node* leaf) {
	Node* retVal = flip(root, leaf);
	if(retVal) {
		return leaf;	// new root
	}
	
	return root;	// could not find target leaf. So return original root
}

Node* flip(Node* root, Node* target) {
	if(root == NULL) 
		return NULL;

	if(root == target && root is leaf) {
		return root;
	}

	Node* L= flip(root->left, target);
	if(L) {
		root -> left = NULL;
		L->right = root;
		return root;
	}

	Node* R= flip(root->right, target);
	if(R) {
		root->right = NULL;
		R->left = root;
		return root;
	}

	return NULL;
}

just delete recursively