114. Flatten Binary Tree to Linked List

Today, I managed to solve a LeetCode medium problem (partially) by myself! I wasn’t very confident at first, but I just followed my thought process and worked through it.

Understanding the Problem

The question was to modify a binary tree so that it becomes a linked list, following a pre-order traversal order. Since I was focusing on DFS questions this week, I initially thought, “Isn’t DFS an in-order traversal?” Instead of fixating on DFS, I decided to logically break down the problem.

Initial Thought Process

1. We want to move all left branches to the right, positioning them before the right branch.
2. To achieve this, we temporarily store the right branch, move the left subtree to the right, then append the original right subtree at the rightmost node of the new right branch.
3. Repeat the process recursively.

My Recursive Solution

class Solution:
    def flatten(self, root: Optional[TreeNode]) -> None:
        """
        Do not return anything, modify root in-place instead.
        """
        if not root:
            return None
        current = root
        if current.left: 
            current = current.left
            temp = root.right  # Placeholder for the original right subtree
            root.right = current  # Move left subtree to the right
            root.left = None  # Remove left link
            while current.right:
                current = current.right  # Traverse to the rightmost node
            current.right = temp  # Append the original right subtree

        self.flatten(root.right)

Space Complexity Issue

My solution used recursion, which requires O(n) additional space due to the depth of recursion. However, the problem specifically required O(1) additional space.

Optimized Iterative Solution

After looking at the solution, I realized my approach wasn’t far off. Instead of using a placeholder, the optimised solution directly appends the right subtree to the rightmost node of the left subtree, then moves the left subtree to the right and continues traversing.

class Solution:
    def flatten(self, root: Optional[TreeNode]) -> None:
        """
        Do not return anything, modify root in-place instead.
        """
        current = root

        while current:
            # If there's a left subtree, move it to the right
            if current.left:
                check = current.left
                while check.right:
                    check = check.right  # Find the rightmost node of left subtree
                check.right = current.right  # Attach original right subtree

                # Move left subtree to the right
                current.right = current.left
                current.left = None

            # Move to the next node on the right
            current = current.right

Final Thoughts

I explained this problem in more detail in my YouTube video:

I'm just grateful that I was able to solve a LeetCode problem today—it means progress! See you all next time!