Copy a binary tree in iterative manner

Question

I was asked this question in an interview, and it literally cost me a job :P The interviewer asked, that you will be given the root to a tree and you have to return the root to the copied tree, but the copy should be made in an iterative manner. I am pasting my code here, I wrote the same there, and it works fine. I initially did this using two stacks, which the interviewer said he didn't like, then I did it in the following way. The interviewer was kinda unhappy about me using another structure that holds a pointer to the original and final tree (refer code).

I am wondering if there any other, better way to do this??

struct node
{
   int data;
   struct node * left;
   struct node * right;
};

struct copynode
{
   node * original;
   node * final;
};

node * copy(node *root)
{
    stack <copynode*> s;
    copynode * temp=(copynode*)malloc(sizeof(copynode));
    temp->original=root;
    temp->final=(node *)malloc(sizeof(node));
    s.push(temp);
    while(s.empty()==false)
    {
       copynode * i;
       i=s.top();
       s.pop();
       i->final=i->original;
       if(i->original->left)
       {
          copynode *left=(copynode*)malloc(sizeof(copynode));
          left->original=i->original->left;
          left->final=(node *)malloc(sizeof(node));
          s.push(left);
       }
       if(i->original->right)
       {
          copynode *right=(copynode*)malloc(sizeof(copynode));
          right->original=i->original->right;
          right->final=(node *)malloc(sizeof(node));
          s.push(right);
       }
   }  
   return temp->final;
}

Answer 1

The first code segment is the solution. The second segment is a file you can copy, paste, and run to see the solution at work.

SOLUTION:

public Node clone() {
    if(null == root)
        return null;
    Queue<Node> queue = new LinkedList<Node>();
    queue.add(root);
    Node n;

    Queue<Node> q2 = new LinkedList<Node>();
    Node fresh;
    Node root2 = new Node(root.data);
    q2.add(root2);

    while(!queue.isEmpty()) {
        n=queue.remove();
        fresh = q2.remove();
        if(null != n.left) {
            queue.add(n.left);
            fresh.left = new Node(n.left.data);
            q2.add(fresh.left);
        }
        if(null != n.right) {
            queue.add(n.right);
            fresh.right= new Node(n.right.data);
            q2.add(fresh.right);
        }           
    }       
    return root2;
}//

PROGRAM FILE:

import java.util.LinkedList;
import java.util.Queue;

public class BST {
Node root;

public BST() {
    root = null;
}

public void insert(int el) {

    Node tmp = root, p = null;
    while (null != tmp && el != tmp.data) {
        p = tmp;
        if (el < tmp.data)
            tmp = tmp.left;
        else
            tmp = tmp.right;
    }
    if (tmp == null) {
        if (null == p)
            root = new Node(el);
        else if (el < p.data)
            p.left = new Node(el);
        else
            p.right = new Node(el);
    }
}//

public Node clone() {
    if(null == root)
        return null;
    Queue<Node> queue = new LinkedList<Node>();
    queue.add(root);
    Node n;

    Queue<Node> q2 = new LinkedList<Node>();
    Node fresh;
    Node root2 = new Node(root.data);
    q2.add(root2);

    while(!queue.isEmpty()) {
        n=queue.remove();
        fresh = q2.remove();
        if(null != n.left) {
            queue.add(n.left);
            fresh.left = new Node(n.left.data);
            q2.add(fresh.left);
        }
        if(null != n.right) {
            queue.add(n.right);
            fresh.right= new Node(n.right.data);
            q2.add(fresh.right);
        }           
    }       
    return root2;
}//

private void inOrder(Node n) {
    if(null == n) return;
    inOrder(n.left);
    System.out.format("%d;", n.data);
    inOrder(n.right);
}//

public static void main(String[] args) {
    int[] input = { 50, 25, 75, 10, 35, 60, 100, 5, 20, 30, 45, 55, 70, 90,
            102 };
    BST bst = new BST();
    for (int i : input)
        bst.insert(i);
    Node root2 = bst.clone();
    bst.inOrder(root2);
}
}

class Node {
public int data;
public Node left;
public Node right;

public Node(int el) {
    data = el;
}
}

Answer 2

If you're allowed to have parent pointers in each node, you don't even need stack:

Walk the original tree and the tree you're creating in parallel. If the current node in the original tree has a left child, but the node in the tree you're creating doesn't, create it and descend left. Similarly with right children. If neither condition applies, go up.

In code (C#):

public static Node Clone(Node original)
{
    if (original == null)
        return null;

    var root = new Node(original.Data, null);
    var clone = root;

    while (original != null)
    {
        if (original.Left != null && clone.Left == null)
        {
            clone.Left = new Node(original.Left.Data, clone);
            original = original.Left;
            clone = clone.Left;
        }
        else if (original.Right != null && clone.Right == null)
        {
            clone.Right = new Node(original.Right.Data, clone);
            original = original.Right;
            clone = clone.Right;
        }
        else
        {
            original = original.Parent;
            clone = clone.Parent;
        }
    }

    return root;
}