114 Flatten Binary Tree to Linked List

Given a binary tree, flatten it to a linked list in-place.

For example, Given

         1
        / \
       2   5
      / \   \
     3   4   6

The flattened tree should look like:

   1
    \
     2
      \
       3
        \
         4
          \
           5
            \
             6

// runs on my comp

• Approach:

  • Create a LL through traversal, and then append to root.

  • Technically O(1) space, since I make to delete the left subtree.

  • O(n), since I just append to root

    Node<T> *head = nullptr;
    Node<T> *front = nullptr;

    void addLL(T val) {
        if (!head) {
            head = new Node<T>(val);
            front = head;
            front->right = nullptr;
            front->left = nullptr;
        }
        else {
            Node<T> *temp = new Node<T>(val);
            front->right = temp;
            front = front->right;
            front->left = nullptr;
            front->right = nullptr;
        }
    }

    void flatten(Node<T> *myroot, Node<T> *parent) {
        if (myroot) {
            flatten(myroot->left, myroot);
            addLL(myroot->value);
            flatten(myroot->right, myroot);

            // recusively remove nodes from bottom - top
            delete myroot;
            myroot = nullptr;
        }

    }

    void printLL() {
        Node<T> *temp = head;
        while (temp) {
            cout << temp->value << " ";
            temp = temp->right;
        }
        cout << endl;
    }

    void flatten(Node<T> *root) {
        flatten(root, nullptr);
        root = head;
        printLL();
        pause();
    }

• Working O(N) space trivial solution

  void flatten(TreeNode* root) {
      if (!root) return;

      TreeNode *t;
      stack<TreeNode*> s;
      s.push(root);

      while (!s.empty()) {
          t = s.top();
          s.pop();
          if (t->right) s.push(t->right);
          if (t->left) s.push(t->left);
          t->left = nullptr;
          t->right = s.empty() ? nullptr : s.top();
      }
  }