CareerCup

Use a stack.
Initialization: push the root in
Iterative steps :
{
1 )pop the top element
2 )Swap left <--> right ptrs.
3 )put them in stack
Repeat until stack is empty
}

The problem says to make a copy, not modify the tree.

Idea is to use two stacks. We do similar pushing and popping for both.

C# like code.

Tree Mirror (Tree root) {
    Stack <Tree> originalStack = new Stack<Tree>();
    Stack <Tree> mirrorStack = new Stack <Tree>();
    
    Tree mirrorRoot = new Tree();
    
    originalStack.Push(root);
    mirrorStack.Push(mirrorRoot);
    
    while (originalStack.IsNotEmpty()) {
        
        Tree node = originalStack.Pop();
        Tree mirrorNode = mirrorStack.Pop();
        
        mirrorNode.Left = new Tree(node.Right); // Assume this constructor copies data and IsLeafNode property
        mirrorNode.Right = new Tree(node.Left); 
        
        if (node.IsLeafNode()) {continue;} // No need to push.
        
        originalStack.Push(node.Left);
        originalStack.Push(node.Right);
        
        mirrorStack.Push(mirrorNode.Right);
        mirrorStack.Push(mirrorNode.Left);
    }
    
    return mirrorRoot;
}

There might be bugs and usage of IsLeafNode is weird (I was too lazy to do null checks), but I hope this gives the basic idea.

Actually using a Queue would be far easier. Do a BFS on the tree, collect all the nodes in a queue. Create a new instance of your BinaryTree class (or whatever it is) and while the queue is not empty, pop element from queue and insert into new BinaryTree...violaa!! you have a clone!

The general algorithm can be given as follows:- (Assuming you have a BinaryTree class, which infact you should, following good OO)

1) binary tree can have a "collect" method that will return a list of all values from it, using BFS (it is very important that you use BFS as it preserves the order in which the nodes were created).

2) Create a new BinaryTree and insert all values from the list on at a time. The new tree will be exactly same as the previous one.