CareerCup

Something along these lines? Though obviously if the "unlimited number" is extremely large, there'd be memory issues...

package printInReverse;

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

public class TreeCopy {
	static class Node
	{
		public Node(int v)
		{
			val = v;
		}
		int val;
		public Node left = null, right = null;
	}
	
	public static void main (String [] args)
	{
		Node n1 = new Node(1);

		Node n2 = new Node(2);
		Node n3 = new Node(3);
		n1.left = n2;
		n1.right = n3;
		
		Node n4 = new Node(4);
		Node n5 = new Node(5);
		n2.left = n4;
		n2.right = n5;

		Node n6 = new Node(6);
		Node n7 = new Node(7);
		n3.left = n6;
		n3.right = n7;
		
		Node copy = copyTree(n1);

		System.out.println(print(n1));
		System.out.println(print(copy));
	}
	
	public static String print(Node n)
	{
		//System.out.println("At " + n.val);
		String s = "";
		if(n.left != null)
			s += print(n.left);
		s += n.val + ", ";
		if(n.right != null)
			s += print(n.right);
		return s;
	}
	
	public static Node copyTree(Node n)
	{
		//Node cur = n;
		Queue <Node> nodesToVisit = new LinkedList();
		nodesToVisit.offer(n);
		
		Node newTreeRoot = copyNode(n);
		Queue <Node> newTreeNodes = new <Node> LinkedList();
		newTreeNodes.offer(newTreeRoot);
		
		while(!nodesToVisit.isEmpty())
		{
			Node cur = nodesToVisit.poll();
			Node newTreeNode = newTreeNodes.poll();
			
			if(cur.left != null)
			{
				Node newLeftNode = copyNode(cur.left);
				newTreeNode.left = newLeftNode;
				nodesToVisit.offer(cur.left);
				newTreeNodes.offer(newLeftNode);
			}
			if(cur.right != null)
			{
				Node newRightNode = copyNode(cur.right);
				newTreeNode.right = newRightNode;
				nodesToVisit.offer(cur.right);
				newTreeNodes.offer(newRightNode);				
			}
		}
		return newTreeRoot;
	}
	
	static Node copyNode(Node n)
	{
		return new Node(n.val);
	}
}

You do BFS traveral of the tree, with a modified queue which holds tuples of the form (node, copied-parent). When a tuple is de-queued from the queue, we create a new node which is a copy of the node in the tuple, and add it as a child of the copied-parent from the tuple.
For each child of the node, we enqueue a tuple (child, new-node).

def tree_copy(root):
  q=new queue()
  q.enqueue((root, None))
  new_root=None
  while (!q.empty()):
    node, new_par=q.dequeue()
    new_node=new Node()
    new_node.val=node.val
    if (!new_root):
      new_root=new_node
    if new_par:
      new_par.children.append(new_node)
    foreach child_node in node.children:
       q.enqueue((child, new_node))

you can do it using two queues.

TreeNode copyTree(TreeNode root){
if(root == null)
return null;

Queue<TreeNode> q1 = new LinkedList<TreeNode>;
Queue<TreeNode> q2 = new LinkedList<TreeNode>;
int level=1;
TreeNode new_root = new TreeNode(root);
TreeNode temp_root = new_root;
TreeNode temp = new TreeNode();
TreeNode marker = new TreeNode("#");

q1.enqueue(root);
q1.enqueue(marker);
q2.enqueue(root.left);
q2.enqueue(root.right);
while(!q1.isEmpty()){
temp = q1.enqueue();
if(temp == marker){
q1.enqueue(temp);
}
else{
q1.enqueue(temp.left);
q1.enqueue(temp.right);
if(level!=1){
q2.enqueue(temp.left);
q2.enqueue(temp.right);
}
temp_root.left = new TreeNode(q2.dequeue());
temp._root.right = new TreeNode(q2.dequeue());
level++
}
}
return new_root;
}

i would probably do the level order traversing.store the values in a list (preserve order).
Then build the new copied tree from that.since left_child=2*i+1 and right is 2*i+2 assuming root node is at index i.repeat this until no nodes..Add zero to list when level order traversal to indicate that its null..

2 queue approach is simplest and correct solution.

Eitherways by unlimited if they mean to look for memory issues, we need to use files, and if the tree was that big in the first place it will be stored in file system anyways - which would only need a file copy to clone - sigh

import java.util.LinkedList;
import java.util.Queue;
import javax.swing.tree.TreeNode;

/**
* copy tree with unlimited number of children with breadth fist search...
*/


public class CopyTreeBFSeg {

/**
* @param args
*/
int data;
CopyTreeBFSeg leftChild, rightChild;
public CopyTreeBFSeg(int data){
this.data = data;
leftChild = null;
rightChild = null;
}
public CopyTreeBFSeg(){}
public CopyTreeBFSeg(CopyTreeBFSeg node){
this.data = node.data;
this.leftChild = null;
this.rightChild = null;
}

public static void main(String[] args) {
// TODO Auto-generated method stub
CopyTreeBFSeg obj = new CopyTreeBFSeg();
CopyTreeBFSeg root = new CopyTreeBFSeg(5);
CopyTreeBFSeg lc = new CopyTreeBFSeg(6);
CopyTreeBFSeg rc = new CopyTreeBFSeg(7);
root.leftChild = lc;
root.rightChild = rc;
CopyTreeBFSeg newRoot = obj.copyTree(root);
System.out.println("new tree: ");
System.out.println(newRoot.data + " ");
System.out.println(newRoot.leftChild.data + " ");
System.out.println(newRoot.rightChild.data + " ");
}
public CopyTreeBFSeg copyTree(CopyTreeBFSeg root){
Queue<CopyTreeBFSeg> nodeQueue = new LinkedList<CopyTreeBFSeg>();
CopyTreeBFSeg newRoot=null;
CopyTreeBFSeg newNode=null, tempNode = null;
CopyTreeBFSeg markerNode= new CopyTreeBFSeg(0);
if(root==null){
return root; //nothing to copy
}
nodeQueue.add(root);
CopyTreeBFSeg newTreeNode = null;
CopyTreeBFSeg parentNode = null;
int lc=0,rc=0;
while(!nodeQueue.isEmpty()){
if(parentNode==null){
parentNode = newTreeNode;
}
tempNode = nodeQueue.remove();
if((tempNode.data==0)&&(lc==0)){
lc=1;
rc=0;
parentNode=parentNode.leftChild;
continue;
}
else if((tempNode.data==0)&&(rc==0)){
lc=0;
rc=1;
parentNode=parentNode.leftChild;
continue;
}

if((parentNode!=null)&&(tempNode.data!=0)){
if(parentNode.leftChild== null){
parentNode.leftChild = tempNode;
}
else{
parentNode.rightChild = tempNode;
}
}
if(tempNode.leftChild!=null){
nodeQueue.add(tempNode.leftChild);

}
if(tempNode.rightChild!=null){
nodeQueue.add(tempNode.rightChild);
nodeQueue.add(markerNode);
}

newTreeNode = new CopyTreeBFSeg(tempNode);
if(newRoot==null){
newRoot = newTreeNode;
}

}
return newRoot;
}

}

You had to write a code for this question or just give him the logic?

why didn't anyone mention that the queue could be a memory concern if it has unlimited children since BFS is preparing children nodes in the queue while it's visiting the nodes on current level?