mutate_tree2.cc

void mutate_tree_bfs(const shared_ptr<BinaryTree> &root) {
    stack<shared_ptr<BinaryTree>> stack1;
    stack<shared_ptr<BinaryTree>> stack2;
    
    stack<shared_ptr<BinaryTree>> *st1 = &stack1;
    stack<shared_ptr<BinaryTree>> &st2 = &stack2;
    
    st1->push(root);
    shared_ptr<BinaryTree> *temp = nullptr;
    bool is_left_most = true;
    
    while (!st1->empty()) {
        auto current = st1.top();
        if (current->left) {
            st2->push(current->left);
        }
        if (current->right) {
            st2->push(current->right)
        }
        
        if (is_left_most) {
            is_left_most = false;
        } else {
            current->left = nullptr;
        }
        
        if (!temp) {
            temp->right = current;
        }
        
        temp = current;
        
        st1->pop();
        if (st1.empty()) {
            temp->right = nullptr;
            temp = nullptr;
            is_left_most = true;
            // switch stack
            st1 = (st1 == &stack1 ? &stack2 : &stack1);
            st2 = (st2 == &stack2 ? &stack1 : &stack2);
        }
    }
}