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
TreeNodeclass where therightchild pointer points to the next node in the list and theleftchild pointer is alwaysnull. - 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
