CareerCup

private static BinaryTreeNode convertToMirror(BinaryTreeNode root) {
		BinaryTreeNode temp;
		if (root != null) {
			convertToMirror(root.getLeft());
			convertToMirror(root.getRight());

			temp = root.getLeft();
			root.setLeft(root.getRight());
			root.setRight(temp);
		}
		return root;
	}

a
b   c

should be

  a
c   b

void mirrorTree(Node btree) {
 if(btree == null) {
   return;
 }
 mirrorTree(btree.left);
 mirrorTree(btree.right);
 tmp = btree.left;
 btree.left = btree.right;
 btree.right = tmp; 
}

Preorder traversal and switch the branch selection logic i.e usually is value < current node go left else go right. make it value < current node go right else go left.

could i run a BFS and maintain an array at each level and keep exchanging but running a pointer at the front and end of the list at each level

xcvcxv

node RevBT(node n){
if(n==null) return null;
node temp = RevBT(n.left);
n.left= RevBT(n.right);
n.right = temp;
return n;
}

The idea is imagining a Btree placed aside a real mirror.
Get the catch ?

left nodes seem right, right nodes seem left.
So, basically it's like, in the new BTree,

newTree->root = createNode(originalTreeRoot->value);
newTree->lChild = <yourMirrorTreeFunction>(originalTree->rChild);
newTree->rChild = <yourMirrorTreeFunction>(originalTree->lChild);

Now, apply this step recursively.
Hope that helps.

void mirror_image(node *root)
{
	if(root != NULL)
	{
		node* temp;
		mirror_image(root->left);
		mirror_image(root->right);
		temp = root->left;
		root->left = root->right;
		root->right = temp;
	}
}

Bst* Bst::getMirror(Bst *root)
{
     if (root == NULL) return NULL;
     if (getMirror(root->left) != NULL || getMirror(root->right) != NULL)
     {
                               Bst *temp;
                               temp = root->left;
                               root->left = root->right;
                               root->right = temp;
     }
     return root;
}

Problem with recursive solutions is that they must traverse to a leaf node before they start to unroll the recursion. The tree may be big, and the recursion stack may take up lots of memory before comparing any node values. Plus recursion is inefficient. BFS is better. Below is Python code to solve the problem for a binary tree. Extension to n-ary tree would be trivial. I'm not claiming it's "good code" -- it's just a proof of concept. The basic idea is to maintain two different queues - one for "left tree" and one for "right tree". Put the left tree root on the left queue, and put the right tree root on the right queue. Then remove one node from each queue and compare values. If lval != rval, return "mirror is broken". Otherwise, put the left node's children on the left queue (left child, then right child) and put the right node's children on the right queue (right child, then left child). Then repeat: remove one node from each queue and compare values. And so on. You only ever maintain enough nodes in the queues to do a BFS in one level of the tree(s). Here's the code:

import Queue

class Node:
    value = -1
    l_child = None
    r_child = None  

L_ROOT = Node()
L_ROOT.value = 1

L_ROOT.l_child = Node()
L_ROOT.l_child.value = 2
L_ROOT.r_child = Node()
L_ROOT.r_child.value = 3

L_ROOT.l_child.l_child = Node()
L_ROOT.l_child.l_child.value = 4
L_ROOT.l_child.r_child = Node()
L_ROOT.l_child.r_child.value = 5

L_ROOT.r_child.l_child = Node()
L_ROOT.r_child.l_child.value = 6
L_ROOT.r_child.r_child = Node()
L_ROOT.r_child.r_child.value = 7

R_ROOT = Node()
R_ROOT.value = 1

R_ROOT.r_child = Node()
R_ROOT.r_child.value = 2
R_ROOT.l_child = Node()
R_ROOT.l_child.value = 3

R_ROOT.r_child.r_child = Node()
R_ROOT.r_child.r_child.value = 4
R_ROOT.r_child.l_child = Node()
R_ROOT.r_child.l_child.value = 5

R_ROOT.l_child.r_child = Node()
R_ROOT.l_child.r_child.value = 6
R_ROOT.l_child.l_child = Node()
R_ROOT.l_child.l_child.value = 7

def mirror_broken(l_root, r_root):
    l_bfs = Queue.Queue(500)
    l_bfs.put(l_root)
    
    r_bfs = Queue.Queue(500)
    r_bfs.put(r_root)
    
    while not (l_bfs.empty() or r_bfs.empty()):
        l_node = l_bfs.get()
        r_node = r_bfs.get()
        if l_node.value != r_node.value:
            return "Mirror is false! left val %d != %d right val" % (l_node.value, r_node.value)
        else:
            print "left val %d == %d right val" % (l_node.value, r_node.value)
            if l_node.l_child and r_node.r_child:
                l_bfs.put(l_node.l_child)
                r_bfs.put(r_node.r_child)
            elif l_node.l_child == None and r_node.r_child == None:
                pass
            else:
                return "Tree structures don't match! (1)"
            if l_node.r_child and r_node.l_child:
                l_bfs.put(l_node.r_child)
                r_bfs.put(r_node.l_child)
            elif l_node.r_child == None and r_node.l_child == None:
                pass
            else:
                return "Tree structures don't match! (2)"
    return "Mirror is True!"
    
print mirror_broken(L_ROOT, R_ROOT)

import java.util.*;

public class BinarySearchTree {
	
	public class Node {
		private int data;
		private Node leftChild, rightChild;
	}

	public static Node mirrorBST(Node node) {
		if (node.equals(null)) return(node);
		
		// swap children of this node
		Node tmp;
		tmp = node.leftChild;
		node.leftChild = node.rightChild;
		node.rightChild = tmp;
			
		// do the subtrees
		if (node.leftChild != null) {
			mirrorBST(node.leftChild);
		}
		if (node.rightChild != null) 
			mirrorBST(node.rightChild);
		return (node);
	} //mirrorBST
	
	public static Node add(Node node, Node tree) {
		Node parent = tree;
		while (tree != null) {
			parent = tree;
			if (node.data < tree.data)
				tree = tree.leftChild;
			else if (node.data > tree.data)
				tree = tree.rightChild;

		}
		if (node.data < parent.data) 
			parent.leftChild = node;
		if (node.data > parent.data)
			parent.rightChild = node;
		// duplicates discarded
		return(tree);
	} //addNode
	
	public static void printTree(Node node) {
		Queue<Node> queue = new LinkedList<Node>();
		if (node == null)
			return;
		queue.add(node);
		queue.add(null);
		while (queue.size() > 0) {
			Node n = queue.poll();
			if (n == null) {
				System.out.println();
				n = queue.poll();
			}
			if (n != null) {
				if (n.leftChild != null)
					queue.add(n.leftChild);
				if (n.rightChild != null)
					queue.add(n.rightChild);
				if ((n.leftChild != null) || (n.rightChild != null))
					queue.add(null);
				System.out.print(n.data+" ");
			}
			
		}	
	}
	
	public static void test(int[] data) {
		Node root = createTree (data);
		printTree(root);
		mirrorBST(root);
		printTree(root);
	}
	
	public static Node createTree (int[] data) {
		int dataLen = data.length;
		BinarySearchTree BST = new BinarySearchTree();
		Node root = BST.new Node();
		root.data = data[0];
		
		for (int i=1;i<dataLen;i++) {
			Node newNode = BST.new Node();
		    newNode.data = data[i];
//		    System.out.println(newNode.data);
		    add(newNode, root);
		}
		return (root);
	}
	
	public static void main(String[] args) {
		int arr1[] = {1};
		test(arr1);
		System.out.println("***");
		int arr2[] = {1,2};
		test(arr2);
		System.out.println("***");
		int arr3[] = {2,1,3};
		test(arr3);
		System.out.println("***");
		int arr4[] = {1,2,3};
		test(arr4);
	} //main

} //BinarySearchTree