CODEWITHSUNDEEP
c++algorithmdata-structurestreebinary-tree
brut3f0rc3
brut3f0rc3

Reputation: 1183

Copy a binary tree in iterative manner

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

Upvotes: 13

Views: 13427

Answers (8)

Waslap
Waslap

Reputation: 571

Doing this iteratively is pretty stupid unless the tree is massive which begs the question why are you copying it in the first place. Here is a C++ attempt which uses copy constructors and hence implicitly recursion.

    struct Node
    {  
        Node *left, *right;
        int value;
        Node() : left(NULL), right(NULL) {}
        Node(const int &_v) : left(NULL), right(NULL), value(_v) {}
        Node(const Node &o) 
        : left(NULL), right(NULL), value(o.value)
        {
            if (o.left)
                left = new Node(*o.left);
            if (o.right)
                right = new Node(*o.right);
        }
        ~Node() { delete left; delete right; }
    };

In other words, you have a tree like so

Node *root = make_a_tree();

Then you copy it like so:

if (root)
    Node *copy = new Node(*root);
else
    Node *copy = NULL;

Upvotes: -1

svick
svick

Reputation: 244787

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

Upvotes: 22

DEEPMALA
DEEPMALA

Reputation: 53

Consider below tree:

                      10
                      / \
                    20   30
                    /\
                  40  50
                      /\
                     60 70

Now based on BFS, if you create an array of nodes ( array is used for faster access), it would be like this:

Array of Nodes: 10 20 30 40 50 N N N N 60 70 N N N N

Index: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

Please note that the indexing is 1 based for easier calculation and children of leaf nodes are denoted as N for NULL.

Now if you will notice that for a node at an index i, its left child is at the index 2*i and its right child is at the index 2*i + 1. This is by the property of a proper binary tree.

Now to copy the binary tree non recursively.

  1. Create an array of nodes from the original tree based on BFS.
  2. Assign current = 1 (current is for index),

  3. Do below while current <= size of array of nodes

    a. create a new node (parent)

    b. Assign the value parent->val from the node at current.

    c. Replace original node at current (index) with the new node. // This step is to be able to traverse through the new nodes.

    d. create a new node, assign to parent->left and assign the value from Lindex = 2*current.

    e. Replace original node at Lindex with the new node.

    f. create a new node, assign to parent->right and assign the value from Rindex = 2*current + 1.

    e. Replace original node at Rindex with the new node.

    f. Increment current by 1.

Now coming to the time complexity,

Since, in the array we also accounted for NULL children of external nodes we need to calculate the total size of the array.

If the number of nodes in the original tree is n, then by the property of binary tree that the number of external nodes of a binary tree is always 1 more than the number of internal nodes, 

 a. Number of external nodes is (n + 1) /2.
 b. Number of children of external nodes (count of all null nodes) is 2 * (n + 1)/2 = n + 1.
 c. Thus the total size of array is number of nodes + number of null nodes = n + n + 1 = 2n + 1

Since in the whole algorithm, we have traversed through the entire array the time complexity of this approach is O(n).

Upvotes: 0

Niras
Niras

Reputation: 455

Java code that works, and has a relatively simple approach:

static Node cloneTree(Node original){
    if(original == null) return null;

    Node temp = original;
    Node root = temp;
    if(original.left!=null)
      temp.left = original.left;
    if(original.right!=null)
      temp.right = original.right;

   cloneTree(original.left);
   cloneTree(original.right);
  return root;
}

Upvotes: -1

rj99999
rj99999

Reputation: 109

Here is my working code :

For each node keep pushing left first, one done pushing left nodes, push the right node and then repeat the same.

#include <iostream>
#include <stack>

using namespace std;

struct Node {
    Node() 
    : left(NULL), right(NULL) {}
    int val;
    Node *left;
    Node *right;
};

struct Wrap {
    Wrap()
    : oldNode(NULL), newNode(NULL), flags(0) {}
    Node *oldNode;
    Node *newNode;
    int flags;
};

void InOrder(Node *node) {
    if(node == NULL) {
        return;
    }
    InOrder(node->left);
    cout << node->val << " ";
    InOrder(node->right);
}

Node *AllocNode(int val) {
    Node *p = new Node;
    p->val = val;
    return p;
}

Wrap *AllocWrap(Node *old) {
    Wrap *wrap = new Wrap;

    Node *newNode = new Node;
    newNode->val = old->val;

    wrap->oldNode = old;
    wrap->newNode = newNode;

    return wrap;
}

Wrap* PushLeftNodes(stack<Wrap*> &stk) {

    Wrap *curWrap = stk.top();  
    while(((curWrap->flags & 1) == 0) && (curWrap->oldNode->left != NULL)) {
        curWrap->flags |= 1;
        Wrap *newWrap = AllocWrap(curWrap->oldNode->left);
        stk.push(newWrap);
        curWrap->newNode->left = newWrap->newNode;
        curWrap = newWrap;
    }
    return curWrap;
}

Node *Clone(Node *root) {

    if(root == NULL) {
        return NULL;
    }

    Node *newRoot = NULL;
    stack<Wrap*> stk;

    Wrap *wrap = AllocWrap(root);
    stk.push(wrap);

    while(!stk.empty()) {
        wrap = PushLeftNodes(stk);
        if(((wrap->flags & 2) == 0) && (wrap->oldNode->right != NULL)) {
            wrap->flags  |= 2;
            Wrap *newWrap = AllocWrap(wrap->oldNode->right);
            stk.push(newWrap);
            wrap->newNode->right = newWrap->oldNode;
            continue;
        }

        wrap = stk.top();
        newRoot = wrap->newNode;
        stk.pop();
        delete wrap;
    }
    return newRoot;
}

int main() {
    Node *root = AllocNode(10);
    Node *curNode = root;

    curNode->left = AllocNode(5);
    curNode->right = AllocNode(15);

    curNode = curNode->left;
    curNode->left = AllocNode(14);

    curNode->right = AllocNode(17);

    curNode = curNode->right;
    curNode->left = AllocNode(18);
    curNode->right = AllocNode(45);

    curNode = root->right;
    curNode->right = AllocNode(33);

    curNode = curNode->right;
    curNode->right = AllocNode(46);

    cout << "Original tree : " << endl;
    InOrder(root);

    Node *newRoot = Clone(root);
    cout << "New tree : " << endl; 
    InOrder(newRoot);

    return 0;
}

Upvotes: 0

kasavbere
kasavbere

Reputation: 6003

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

Upvotes: 3

andrew cooke
andrew cooke

Reputation: 46882

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

Upvotes: 1

mah
mah

Reputation: 39807

One method without recursion would be to walk through each node, and if the node contains a right branch, push that right node onto a stack. When you run out of nodes along your path (following only those nodes with left branches), pop the top node off the stack and follow it using the same rules (push the right, then follow the left). Repeat this loop until your stack is empty. This should only require a single stack.

Edit: Did you ask the interviewer what method s/he was looking for? If not, you should have, in a manner that suggests your willingness to learn new things and you should have tried to make it a two-way dialog. I'm sure you do have that willingness to learn new things (or you would not have posted here), but did your interviewer know this? Keep in mind -- interviewers are generally not looking for a specific answer to things, but rather they're looking to evaluate your approach to solving them, and not purely in a technical manner. If you didn't engage this way, you made it impossible for the interviewer to consider that you don't know everything but are able to learn and might make a great addition to their team.

Upvotes: 0

Related Questions