# 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> *front = nullptr;
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);
flatten(myroot->right, myroot);
// recusively remove nodes from bottom - top
delete myroot;
myroot = nullptr;
}
}
void printLL() {
while (temp) {
cout << temp->value << " ";
temp = temp->right;
}
cout << endl;
}
void flatten(Node<T> *root) {
flatten(root, nullptr);
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();
}
}