[Top Interview 150] 114. Flatten Binary Tree to Linked List

Solution)

class Solution:
    def flatten(self, root: Optional[TreeNode]) -> None:
        # Base Case
        if not root: return
        
        # Initialization
        arr = []

        # Helper func that adds nodes to arr in preorder
        def preorder(root):
            if not root: return None

            arr.append(root)

            preorder(root.left)
            preorder(root.right)
        
        preorder(root)

        # Connect nodes through right attribute
        cur = root
        for i in range(1, len(arr)):
            cur.left = None
            cur.right = arr[i]
            cur = cur.right

 
Problem: LeetCode
 
Time Complexity: O(n)
Space Complexity: O(1) *uncertain
 

Explanation)

We'll iterate a binary tree in a preorder traversal and save the nodes in a separate space.
 
Then connect the saved nodes in a flattened way by connecting them through their right attributes.
 

1. Base Case & Initialization)

If there is no binary tree, we have nothing to flatten so return None.
 
Our array arr will save nodes in preorder.
 

def flatten(self, root: Optional[TreeNode]) -> None:
        # 1. Base Case & Initialization
        if not root: return
        
        arr = []

 

2. Helper Function)

Now we'll make a helper function preorder that will save nodes to arr in preorder. A simple recursive function that appends nodes to arr in preorder.
 
Don't forget to execute the helper function.
 

def flatten(self, root: Optional[TreeNode]) -> None:
        # 1. Base Case & Initialization
        if not root: return
        
        arr = []

        # 2. Helper function
        def preorder(root):
            if not root: return None

            arr.append(root)

            preorder(root.left)
            preorder(root.right)
        
        preorder(root)

 

3. Connect nodes through right attribute)

Now connect the nodes as saved in arr.
 
While connecting them through their right attributes, make sure to set their left as None to completely flatten the tree.
 

def flatten(self, root: Optional[TreeNode]) -> None:
        # 1. Base Case & Initialization
        
        # 2. Helper function
        def preorder(root):
            if not root: return None

            arr.append(root)

            preorder(root.left)
            preorder(root.right)
        
        preorder(root)

        # 3. Connect nodes through right attribute
        cur = root
        for i in range(1, len(arr)):
            cur.left = None
            cur.right = arr[i]
            cur = cur.right

 
 
 
Honestly, not the best solution. I couldn't come up with a clever solution of not using extra space. I tried recursions, but kept on overwriting my nodes.