question

Design an algorithm to flatten a binary tree into a linked list, breadth-first. Implement this with constant storage.

Use different sides of the tree (left vs right) to help in building your list.

The general idea is to built the linked list along the left children of the tree. The right side of the tree will be used to hold a queue of the next subtrees to insert. There is a great answer online for this question, but it is too long to copy below. Check out the answer on StackOverflow.

Thoughts or alternate solution? Let us know in the comments below!

Thoughts or alternate solution? Let us know in the comments below!