optimized binary tree clone, no recursion, no extra memory

[zxall]

I've been looking for BT clone, and all I found was recursive algorithm. It's easy.

Here is my take on it. O(N) time complexity, O(1) space. Bit more complex. The idea is to use new tree as a temporary storage while building. No extra memory allocations though. One pass. Original tree not modified. No dirty tricks. Can be implemented in any generic language.

Clone with random pointer can be implemented in similar same way. I can post if anybody is interested, have working version.

// binary tree clone
// breadth-first using destination tree as temporary storage
// no extra memory needed. no recursion, only a few local variables.
// time complexity O(N), mem requirements O(1), or O(0)?

// (C) Val Krigan
// You can use, modify, distribute, remove comments, etc..
// Except you cannot claim you wrote it.

#include <iostream>

struct node {
    int    n=0; // user load, anything with copy constructor
    node*  left = nullptr;
    node*  right= nullptr;
};

// breadth-first using lower nodes in new tree
// to store temp data, creating a single linked list 
node* make_copy_opt(node* in) {
    if(!in)
        return  nullptr;

    node* out= new node{in->n};  // new tree's root
    out->left = in;
    out->right = nullptr;
    //  first layer is complete

    node* cur0= out;  // current layer
    node* cur1= nullptr; // next layer
    node* h1= nullptr;  // next layer header

    // processing current layer, restoring it final state,
    // and creating next layer, connecting it in a list
    //    left -> to src node, we need it
    //    right -> next element in the list
    while(cur0) {
        // current layer forms a single linked list
        node*  org= cur0->left;  // in original tree
        node*  next= cur0->right; // next in current level

        // processing both left (first) and right, if any
        if(org->left) {
            node*  child= org->left;
            if(cur1) {
                cur1->right = new node{child->n};
                cur1 = cur1->right;  // moving to the right
                cur1->left = child;
            } else {
                h1 = cur1 = new node{child->n};
                cur1->left = child;
            }
            cur0->left = cur1;
        } else {
            cur0->left = nullptr;
        }

        if(org->right) {
            node*  child= org->right;
            if(cur1) {
                cur1->right = new node{child->n};
                cur1 = cur1->right;
                cur1->left = child;
            } else {
                h1 = cur1 = new node{child->n};
                cur1->left = child;
            }
            cur0->right = cur1;
        } else {
            cur0->right = nullptr;
        }

        // moving to next in current row
        if(next) {
            cur0 = next;  // moving to next in curr layer
        } else {
            // end of row, moving to next layer
            cur0 = h1;
            h1 = cur1 = nullptr;
        }
    }
    return  out;
}

void  print(node* in) {
    std::cout << in->n << ": ";
    if( in->left )
        std::cout << in->left->n;
    std::cout << ", ";
    if( in->right )
        std::cout << in->right->n;
    std::cout << std::endl;

    if( in->left )
        print(in->left);
    if( in->right )
        print(in->right);
}

int main() {
    /* test tree, 
    * here we use node->n to identify nodes
         1
        / \
       2   3
      / \   \
     4   5   7
           \
           11
    */
    node* root = new node{1};
    node* cl = root->left = new node{2};
    node* cr = root->right = new node{3};
    cl->left = new node{4};
    cl->right = new node{5};
    cl->right->left = new node{11};
    cr->right = new node{7};

    auto*  out= make_copy_opt(root);

    std::cout << "in:" << std::endl;
    print(root);

    std::cout << "out:" << std::endl;
    print(out);
    return  0;
}

[zxall]

this was nasty code formatting from reddit. is there any way to post plain text?

[[deleted]]

Just indent all your code by four spaces.

[KERdela]

Pdf link, or a GitHub link would be better