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

Solution 1

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

Solution 2

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

Solution 3

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".

Comments

[brut3f0rc3]

thanks for the input, but i see you have used two queues, i was wondering if some better space complexity is possible for this!!

[brut3f0rc3]

looking back to your approach, if i push the right child of any node, traverse along its left branch, and later face a NULL, i am left with a stack with a right child pushed in, but how do i determine which node's right child is it, so that i can properly make the same insertion in the final tree??? ps: yes, i did ask the interviewer, and he was just like "you are forgetting some basic property of trees, that would make the solution easy", and never figured out what property he was referring to.

[brut3f0rc3]

and then what?? once the left branch has been traversed, we need to look up in the stack, make a search for that node in the copied tree, and proceed.. the searching further increases the complexity man!!!

[mah]

I think to solve the "where did this node come from?" problem you may need to deal with pushing a meta-node instead. The meta-node would include the original node as well as a position it belongs in. I do not know offhand what the "basic property to make the solution easy" is, but I suspect it's something that would immediately make sense.

[brut3f0rc3]

and i am puzzled too :) but, thanks for your inputs, always nice to know new ways!!!

[brut3f0rc3]

can you please elaborate the first part.. i mean, what do you mean by " add nodes to the copy's root. "?? could you give a brief algo for that??

[andrew cooke]

just call the normal subroutine that you would call when adding a new value to the tree. it starts at the root and branches down through the tree until it adds a new leaf node.

[andrew cooke]

oh, sorry, i assumed it was. [edit:] if it's not, how are nodes added? depending on what the algorithm is. this may still work with the correct traversal.

[brut3f0rc3]

well,that has not been given, you just have the tree with you, that's it!!

[andrew cooke]

well, no. you're not at college. it's not an exam. it's a social situation with imperfect people where commmunication pays an important role. perhaps it was a bst - perhaps the questioner was assuming that too? you seem to be more interested in proving yourself right in some kind of imaginary classroom than exploring what might have been and how, frankly, you screwed up.

[kasavbere]

Traveling a tree in level order (aka Breadth First Search) will always require a queue. In fact all BST traversals require either stacks or queues whether implicit or explicit. As far as space complexity, note that together the two queues worst case for a BST with n nodes is: 2(n/2+1) = n+2 = O(n): that's the worst case of the entire algorithm! So if you were not cloning traversal would take you O(n); cloning with this algorithm still takes you O(n)!

[brut3f0rc3]

hahaha.. that shows your frustration man, at not being able to solve it, because you have been trying rather desperately to prove your move right..Hey, i am not trying to prove myself right, coz i know my solution lacked somewhere, but please, i am looking for a better approach, rather than super simplifying the case by making it a BST, and then trying to justify myself by giving stupid logics like " it's a social situation with imperfect people where commmunication pays an important role. perhaps it was a bst - perhaps the questioner was assuming that too"... thanks for your efforts though!

[andrew cooke]

no, i have a job. curiously, i'm doing this to try help you.

[brut3f0rc3]

Oh, i get it, you think i don't have a job.. hahaha.. well, suit yourself man, whatever keeps you happy!! ps: with due respect man, i know you are much more experienced than me,probably know a lot more than me, but this one, i am not trying to "PROVE" something!!

[kasavbere]

Note that the O(n) is referring to space complexity -- although time complexity is also O(n)

[brut3f0rc3]

okay, how come it is 2(n/2+1)??? you are pushing every node inside the queue once for the original tree and once for the final tree, so it is 2(n)... now agreed, the space complexity is O(n), but so is in the case of my solution.

[kasavbere]

"how come it is 2(n/2+1)???" It's not. I was tutoring someone about printing a tree by level while answering your question.

[Sumit Kandoi]

my tree struct is like public static class TreeNode{ int data; TreeNode left; TreeNode right; TreeNode randomNode;} how i will call clone.Parent

[Kevman]

@SumitKandoi without parent node(pointer), you'll need a stack/queue