We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Flatten Binary Tree to Linked List

Number: 114

Difficulty: Medium

Paid? No

Companies: Google, Meta, Amazon, Microsoft, Bloomberg, Oracle, Media.net, Adobe, Yahoo, Anduril

Problem Description

Given the root of a binary tree, transform the tree into a "linked list" in-place following the pre-order traversal. In the resulting tree, every node’s left pointer should be null and the right pointer should point to the next node in the pre-order sequence.

Key Insights

  • The goal is to rearrange the tree without using extra space for new nodes or data structures.
  • A pre-order traversal order must be maintained, meaning the current node is processed before its left and right children.
  • One in-place solution involves iterating over nodes, finding the rightmost node in the left subtree (if it exists), attaching the original right subtree to this node, then moving the left subtree to the right.
  • Using an iterative approach can achieve O(1) extra space, while a recursive solution may use stack space proportional to the tree height.

Space and Time Complexity

Time Complexity: O(n) where n is the number of nodes (each node is processed a constant number of times).
Space Complexity: O(1) extra space in the iterative solution (ignoring recursion stack in the recursive approach).

Solution

We use an iterative approach to flatten the tree. The idea is to start from the root and for each node:

  1. If a left child exists, locate the rightmost node of the left subtree.
  2. Attach the node’s existing right subtree to the right pointer of this rightmost node.
  3. Move the left subtree to the right pointer of the current node and set the left pointer to null.
  4. Move to the next node (which is now the right child) and repeat until all nodes have been processed.

This approach effectively re-links all nodes following a pre-order traversal and avoids the overhead of extra space (aside from loop variables).

Code Solutions

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right

def flatten(root):
    # Start from the root node
    current = root
    # Iterate until we have processed all nodes
    while current:
        # If current node has a left subtree
        if current.left:
            # Find the rightmost node in the left subtree
            rightmost = current.left
            while rightmost.right:
                rightmost = rightmost.right
            # Connect the original right subtree to the rightmost node
            rightmost.right = current.right
            # Move the left subtree to become the right subtree
            current.right = current.left
            # Set the left child to None as per linked list requirement
            current.left = None
        # Move to the next right node in the flattened list
        current = current.right
← Back to All Questions