Binary Trees and Linked Lists — Flatten Binary Tree to Linked List

In todays problem we are going to be flattening a binary tree to a linked list.

This is a fairly straight forward problem. We will need to iterate through each node and keep track of each node in our binary tree. We do this by calling a depth first search function on our tree. This will be a preorder traversal since we want everything in sequential order.

Once we search our tree, we are left with an array that contains the nodes (and subtrees) of our original binary tree. Now we need to connect these nodes into a binary tree that represents a linked list. This means our tree can only have right child nodes. Now we will iterate through our order array. At each index we set the left child node equal to null and we set the right child node equal to the next node in our order array.

Lets see an example: