By Long Luo

The Binary Tree Traversal Algorithms can be find here Tree Traversal Algorithms: PreOrder, InOrder and PostOrder.

We can use DFS to traversal the binary tree.

# PreOrder + List

It’s easy to find that the flatten tree is the PreOrder of the tree. We can preorder the tree and store the TreeNodes in a List.

Traversal the list, make the current node as the preNode’s right node.

We can also traversal the tree iteratively with a Stack:

## Analysis

• Time Complexity: $O(n)$.
• Space Complexity: $O(n)$.

# Iteration

The Process is as follows:

Let’s coding it.

## Analysis

• Time Complexity: $O(n)$.
• Space Complexity: $O(n)$.

# Recursion

To Flatten Binary Tree to Linked List, there are 3 steps as the picture shows.

1. Flatten the left subtree of the root node into a linked list;
2. Flatten the right subtree of the root node into a linked list;
3. Let the right subtree of the step 2 be the right child of the farest right node of the left subtree of step 1.

Obiously, that’s a recursion process.

Let’s coding it.

## Analysis

• Time Complexity: $O(n)$.
• Space Complexity: $O(n)$.

# References:

All suggestions are welcome.
If you have any query or suggestion please comment below.
Please upvote👍 if you like💗 it. Thank you:-)

Explore More Leetcode Solutions. 😉😃💗