Copy a binary tree in iterative manner

two ideas:

1. you need either a stack or parent links to traverse the input tree (afaict). so let's assume that the interviewer would be happy with one of those. what is left to simplify?

   in your code you also traverse the copy storing its nodes in parallel with your original. instead, you could simply add nodes to the copy's root. as long as you chose the traversal of the original correctly, you would end up with the same structure.

   and it's not hard to see that pre-order traversal would do this (assuming no re-balancing on addition).

   so you could write your copy in terms of pre-order traversal plus simple addition to the copy root. this would give simpler code and/or allow re-use, at the cost of being less efficient (you have O(nlog(n)) extra "hops" to find the correct places in your copy on insertion).

2. for immutable nodes, you only need to copy the root (this is normal functional style).

my gut feeling is that (1) may be what he was looking for, given the reference to "properties of a tree".

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;
}
}

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;
}