Nerd For Tech
Published in

Nerd For Tech

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 = [0]
Output: [0]

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

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store