CareerCup

reverse(node* ptr)
{
   if(ptr==null)
        return;
  else{

  reverse(ptr->left);
  reverse(ptr->right);
  node* t= ptr->left;
  ptr->left=ptr->right;
  ptr->right=t;
  return;
  }
}

Finally a brute force method BigO is (3N) 2N for Traversal and N for pointer adjustment.
I accept it takes more memory, so champs please come up with something more optimize and elegant.

/// <summary>
/// Reverses a Balanced Bindary Tree
/// </summary>
/// <param name="rroot"></param>
/// <returns></returns>
private ArrayList ReverseTree(TNode root)
{
ArrayList nodes = new ArrayList();
ArrayList heads = new ArrayList();
TNode curr, left, right;

PostOrder_Reverse(root, nodes);

for (int i = 0; i < nodes.Count; i++)
{
curr = nodes[i] as TNode;

if (curr.right == null)
{
heads.Add(curr);
continue;
}
else
{
left = curr.left;
left.left = curr;
left.right = null;
curr.left = null;

right = curr.right;
right.left = curr;
right.right = null;
curr.right = null;
}
}

return heads;
}


/// <summary>
/// Populate input ArrayList while traversing in postorder (L R N)
/// </summary>
/// <param name="ptr"></param>
/// <param name="nodes"> </param>
private void PostOrder_Reverse(TNode ptr, ArrayList nodes)
{
if (ptr != null)
{
PostOrder_Reverse(ptr.left, nodes);
PostOrder_Reverse(ptr.right, nodes);
nodes.Add(ptr);
}
}

I think we should do sth like post-order traversal...
reverse(treeptr *ptr, treeptr parent)//Call as reverse(&root,NULL);
{
if(*ptr)
{
if((*ptr)->left || (*ptr)->right)
{
parent = *ptr;
}
reverse((*ptr)->left);
reverse((*ptr)->right);
(*ptr)->left = parent;
(*ptr)->right = NULL;
}
}

Can you specify more clearly what's a "revert Binary tree"?

Node[] Reverse(Node root)

so for the tree below, out put shd be Array with 4 roots L1,L2,L3,L4

Input Tree:

R
C1 C2
L1 L2 L3 L4

Output tree: (Its No more binary tree, looks like a 4 linked list where L1,L2 share common Node C1 and R, and L3 L4 has common node C2 and R)

L1 L2 L3 L4
C1 C2
R

use bfs level order traversing .
save all the same level nodes into a array(level wise).
now you can print the array in reverse order.

code is in C# and "///" denote commented line

Please comment

void ReveseTree(Tree** root)
{
reverseT(root,NULL);
}

void ReverseT(Tree** root, Tree* parent)
{
if(!root) return NULL;
Tree* node=*root;
if(!node) printTree(parent);

Tree* left=NULL;
Tree* right=NULL;

if(node)
{
*root=node;
left=node->left;
right=node->right;
node->left=parent;
parent=node;
reverseT(left,parent);
reverseT(right,parent);
}
}

void printTree(Tree* root)
{
//any order traverse here
}

a correction
void ReveseTree(Tree** root)
{
reverseT(root,NULL);
}

void ReverseT(Tree** root, Tree* parent)
{
if(!root) return NULL;
Tree* node=*root;
if(!node)
{printTree(parent);
return;
}


Tree* left=NULL;
Tree* right=NULL;

if(node)
{
*root=node;
left=node->left;
right=node->right;
node->left=parent;
parent=node;
reverseT(left,parent);
reverseT(right,parent);
}
}

void printTree(Tree* root)
{
//any order traverse here
}

sorry more correction.
print and return when it is a leaf node;otherwise, continue recursion
void ReveseTree(Tree** root)
{
reverseT(root,NULL);
}

void ReverseT(Tree** root, Tree* parent)
{
if(!root) return NULL;
Tree* node=*root;

Tree* left=NULL;
Tree* right=NULL;

if(node)
{
*root=node;
left=node->left;
right=node->right;
node->left=parent;
if(!right&&!left)
{
printTree(node);
return;
}
parent=node;
reverseT(left,parent);
reverseT(right,parent);
}
}

void printTree(Tree* root)
{
//any order traverse here
}

One problem i see is you will lose the tree.
As after reversal it will multiple roots, so you Reverse() shd return a Array of root nodes. so for example above Reverse() return array
heads[0]=L1
heads[1]=L2
heads[2]=L3
heads[3]=L4

Did it by any chance mean doing a mirror image of the tree OR in other words rotating it around the root, so if the storing order is left child < parent < right child (increasing order left to right), then reversal will result in left child > parent > right child (increasing order right to left) ?

hipy... see the example in 3rd post. its not the way u said.

In ur words :)
Flip the tree vertically ... and change the --> to <---

storing of the reversed tree is trivial, just replace the print statement with some code to store them

i think we shld go for breadth first search on the given complete binary tree.. and storing each node in an array . (R C1 C2 L1 L2 L3 L4)

now we can generate the tree as .. at any level i the node will have two parents at i+1 th level ie left parent and right parent . and so on ..
for eg . R will have L1 as left parent and L2 as Right parent .
L1 will have C1 as left parent and C2 as right parent .

if array Nodes [] stores the node then ..
for i th node in the array .
the Left parent wud be i*2
the right parent wud be i*2+1

this way we can make the given tree.

Comments are invited

I think this is not that complicated. Do things like the following,
Just use the left link as the next pointer.
Node[] reverseTree(node *r){
//first get the number of leaves, create an array nodes[];
reverse(r, nodes);
return nodes;
}

Node *reverse(Node *r, nodes){
static int cnt = 0;
if(!r) return;
Node *left = reverse(r->left, nodes);
Node *right = reverse(r->right, nodes);
if(!left && !right){ nodes[cnt++] = r; return r;}
if(left) left->left = r;
if(right) right->left = r;
return r;
}

/*
root -> binary tree handle
i -> no. of root handles in the array (when the function returns), passed in as a reference
array -> container for the root's to be returned.
*/


node *array[100];
int i(0);
reverse_binarytree(array, root, i);
// loop through array for i iteration's and print out each as a regular linked list.



int reverse_binarytree(node** array, node* root, int & i){
if(!root)
return 0;
if((!root->lptr) && (!root->rptr)){
array[i++] = root;
return 0;
}
if(root->lptr) reverse_binarytree(array, root->lptr,i);
if(root->rptr) reverse_binarytree(array, root->rptr,i);
if(root->lptr) root->lptr->lptr = root;
if(root->rptr)root->rptr->lptr = root;
root->lptr=root->rptr=0;
return 0;
}

will this approach work:

reverse( root )
{
//Check of the left child is a leaf
if ( root->left != NULL and
root->left->left == NULL and
root->left->right == NULL )
root->left->right = root ;
root->left = NULL ;
if( root->right != NULL and
root->right->left == NULL and
root->right->right === NULL )
root->right->left = root ;
root->right = NULL
return ;
}

reverse ( root->left ) ;
root->left->right = root ;
reverse ( root->right ) ;
root->right->left = root ;
}

Please comment:

reverse(node *node){
node *tmp;

if(node==NULL)
return NULL;
if(node->left) {
tmp=node->left;
tmp->right=node;
node->left=NULL;
reverse(tmp);
}
if(node->right) {
tmp=node->right;
tmp->left=node;
node->right=NULL;
reverse(tmp);
}
}

guys avoid posting crappy bunch of codes without any explanation

/// <summary>
        /// Reverse a Binary Tree (not BST)
        /// Interviewer started with giving me a sample of 
        /// balance binary tree with Depth 3 i.e. total 7 nodes.
        /// </summary>
        /// <returns></returns>
        public List<node> Reverse()
        {
            list = new List<node>();
            ReverseTree(root, null);
            return list; 
        }

        private void ReverseTree(node rootptr,node rootroot)
        {
            node temp;
            if (rootptr.left != null)
            {
                ReverseTree(rootptr.left,rootptr);
            }

            if (rootptr.right != null)
            {
                ReverseTree(rootptr.right,rootptr);
            }

            if ((rootptr.left == null) && (rootptr.right == null))
            {
                list.Add(rootptr);
            }

            if (rootroot != null)
                rootptr.left = rootroot;
         }

Reverse binary tree is nothing but mirror image of binary tree.
look at the link "en.literateprograms.org/Binary_tree_(Scheme)"

void reverse (Node *node)
{
    if (node == NULL)
        return;
    if (node->left != NULL && node->left->left == NULL && node->left->right == NULL)
    {
        node->left->right = node;
        node->left = 0;
    }
    if (node->right != NULL && node->right->left == NULL && node->right->right == NULL)
    {
        node->right->left = node;
        node->right = 0;
        if (node->left == NULL)
            return;
    }
    if (node->left == NULL && node->right == NULL)
        return;
    if (node->left)
    {
        reverse (node->left);
        node->left->right = node;
        node->left = NULL;
    }
    if (node->right)
    {
        reverse (node->right);
        node->right->left = node;
        node->right = 0;
    }
}

private Node<T> reverse(Node<T> root) {
if (root == null) {
return null;
} else {
Node<T> left = root.getRight();
root.setRight(reverse(root.getLeft()));
root.setLeft(reverse(left));
}

return root;
}

void reverse(Node *n) {
if (n == null) return;
if ( (n->left != null) && (n->right !=null)) {
Node *t = node->left;
node->left = node->right;
node->right = t;
}

if (node->left !=null) {
reverse(node->left);
}

if (node->right != null) {
reverse(node->right);
}
}

My solution is a recursive traversal with recording the parent node of the current node and whether the current node is the left child of its parent node. A test case and class TreeNode are attached also.

public class TreeNode
{
	public TreeNode left=null;
	public TreeNode right=null;
	int val;
	public TreeNode(int v)
	{
		val=v;
	}
	public String toString()
	{
		return String.format("[TreeNode: val=%d]", val);
	}
	public String toStringAll()
	{
		return String.format("[TreeNode: val=%d, left=%s, right=%s]", val, 
				(left!=null) ? left.toStringAll() : null, 
				(right!=null) ? right.toStringAll() : null);
	}
}
public class ID60068
{
	public ArrayList<TreeNode> reverseBinaryTree(TreeNode root)
	{
		ArrayList<TreeNode> resultList=new ArrayList<TreeNode>();
		reverseBinaryTree(root, null, true, resultList);
		return resultList;
	}
	
	private void reverseBinaryTree(TreeNode root, TreeNode parentNode, boolean isLeft, ArrayList<TreeNode> resultList)
	{
		if (root==null)
			return;
		reverseBinaryTree(root.left, root, true, resultList);
		reverseBinaryTree(root.right, root, false, resultList);
		if (root.left==null && root.right==null)
			resultList.add(root);
		if (isLeft)
		{// originally this node is the left child of its parent node
			root.left=null;
			root.right=parentNode;
		}
		else
		{
			root.left=parentNode;
			root.right=null;
		}
	}
	
	public static void main(String[] args)
	{
		TreeNode root=new TreeNode(1);
		root.left=new TreeNode(2);
		root.right=new TreeNode(3);
		root.left.left=new TreeNode(4);
		root.left.right=new TreeNode(5);
		root.right.left=new TreeNode(6);
		root.right.right=new TreeNode(7);		
		
		System.out.println(root.toStringAll());
		
		ID60068 wpd=new ID60068();
		System.out.println(wpd.reverseBinaryTree(root));
	}

}

You can use right root left to traverse in reverse order.

you can use right root left

(1) go for simple inorder traversal
(2) make each node's(not the root) left pointer pointing to its parent
(3) whenever you get a leaf, add it to the linked list