# Swift Leetcode Series: Flatten Binary Tree to Linked List

## Swift + Binary Trees + Linked List = Leetcode 114 ✅✅✅

Check the full story on The Swift Nerd blog with the link above.

# Problem Description

Given the `root` of a binary tree, flatten the tree into a “linked list”:

• The “linked list” should use the same `TreeNode` class where the `right` child pointer points to the next node in the list and the `left` child pointer is always `null`.
• The “linked list” should be in the same order as a pre-order traversal of the binary tree.

# Examples

`Input: root = [1,2,5,3,4,null,6]Output: [1,null,2,null,3,null,4,null,5,null,6]Input: root = []Output: []Input: root = Output: `

# Constraints

• The number of nodes in the tree is in the range `[0, 2000]`.
• `-100 <= Node.val <= 100`

Follow up: Can you flatten the tree in-place (with `O(1)` extra space)?

# Solution

We can intuitively think of a recursively approach to traverse the list in preorder approach and recursively convert the left and right subtrees as skewed trees.

After recursively solving the left and right subtrees, all we need to do is fix some pointers with respect to the room. This recursion would move bottom-up and by the time root node is processed, we are sure that we have already converted the left and right subtrees. Now keep a pointer to traverse the rightmost node in the left subtree (this is needed to connect the right subtree as tail). When we reach the terminal node in the left subtree, simply set the left subtree as root’s right and connect the original right subtree with the terminal left node’s right.

# Follow Up: O(1) Space?

Follow the blog for the optimised solution.

# Complexity Analysis

Time = O(N)

Space = O(N) (Stack Space for recursion).

Thank you for reading. If you liked this article and found it useful, share and spread it like wildfire!

You can find me on TheSwiftNerd | LinkedIn | Github

--

--