CODEWITHSUNDEEP
algorithmdata-structuresbinary-treebinary-search-tree
GoodEgg
GoodEgg

Reputation: 43

Implementing an Iterative Single Stack Binary Tree Copy Function

As a thought exercise I am trying to implement an iterative tree (binary or binary search tree) copy function.

It is my understanding that it can be achieved trivially:

I have written different implementations that meet the inverse of the above constraints but I am uncertain how to approach the problem with the constraints.

I did not see anything in Algorithms 4/e and have not seen anything online (beyond statements of how trivial it is). I considered using the concepts from in order and post order of a current/previous var but I did not see a way to track accurately when popping the stack. I also briefly considered a hash map but I feel this is still just extra storage like the extra stack.

Any help in understanding the concepts/idioms behind the approach that I am not seeing is gratefully received.

Thanks in advance.

Edit:

Some requests for what I've tried so far. Here is the 2 stack solution which I believe is supposed to be able to turn into the 1 stack the most trivially.

It's written in C++. I am new to the language (but not programming) and teaching myself using C++ Primer 5/e (Lippman, Lajole, Moo) [C++11] and the internet. If any of the code from a language perspective is wrong, please let me know (although I'm aware Code Review Stack Exchange is the place for an actual review).

I have a template Node that is used by other parts of the code.

template<typename T>
struct Node;

typedef Node<std::string> tree_node;
typedef std::shared_ptr<tree_node> shared_ptr_node;

template<typename T>
struct Node final {

public:
    const T value;
    const shared_ptr_node &left = m_left;
    const shared_ptr_node &right = m_right;

    Node(const T value, const shared_ptr_node left = nullptr, const shared_ptr_node right = nullptr) : value(value), m_left(left), m_right (right) {}

    void updateLeft(const shared_ptr_node node) {
        m_left = node;
    }

    void updateRight(const shared_ptr_node node) {
        m_right = node;
    }

private:
    shared_ptr_node m_left;
    shared_ptr_node m_right;
};

And then the 2 stack implementation.

shared_ptr_node iterativeCopy2Stacks(const shared_ptr_node &node) {

    const shared_ptr_node newRoot = std::make_shared<tree_node>(node->value);

    std::stack<const shared_ptr_node> s;
    s.push(node);

    std::stack<const shared_ptr_node> copyS;
    copyS.push(newRoot);

    shared_ptr_node original = nullptr;
    shared_ptr_node copy = nullptr;

    while (!s.empty()) {

        original = s.top();
        s.pop();

        copy = copyS.top();
        copyS.pop();

        if (original->right) {
            s.push(original->right);

            copy->updateRight(std::make_shared<tree_node>(original->right->value));
            copyS.push(copy->right);
        }

        if (original->left) {
            s.push(original->left);

            copy->updateLeft(std::make_shared<tree_node>(original->left->value));
            copyS.push(copy->left);
        }
    }

    return newRoot;
}

Upvotes: 1

Views: 529

Answers (1)

user4668606
user4668606

Reputation:

I'm not fluent in c++, so you'll have to settle with pseudocode:

node copy(treenode n):
    if n == null
        return null

    node tmp = clone(n) //no deep clone!!!

    stack s
    s.push(tmp)

    while !s.empty():
        node n = s.pop()

        if n.left != null:
            n.left = clone(n.left)
            s.push(n.left)
        if n.right != null:
            n.right = clone(n.right)
            s.push(n.right)

    return tmp

Note that clone(node) is not a deep-clone. The basic idea is to start with a shallow-clone of the root, then iterate over all children of that node and replace those nodes (still references to the original node) by shallow copies, replace those nodes children, etc.. This algorithm traverses the tree in a DFS-manner. In case you prefer BFS (for whatever reason) you could just replace the stack by a queue. Another advantage of this code: it can be altered with a few minor changes to work for arbitrary trees.

A recursive version of this algorithm (in case you prefer recursive code over my horrible prosa):

node copyRec(node n):
    if n.left != null:
        n.left = clone(n.left)
        copyRec(n.left)

    if n.right != null:
        n.right = clone(n.right)
        copyRec(n.right)

    return n

node copy(node n):
    return copyRec(clone(n))

EDIT:
If you want to have a look at working code, I've created an implementation in python.

Upvotes: 1

Related Questions