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

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Flatten Binary Tree to Linked List

Difficulty: Medium

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.

Key Insights

  • The problem requires traversing a binary tree and converting it into a linked list structure.
  • The linked list should maintain the order of nodes as they appear in a pre-order traversal (root, left, right).
  • The flattening must be done in-place, which means we cannot use additional data structures like arrays or lists to store nodes.

Space and Time Complexity

Time Complexity: O(n) - where n is the number of nodes in the tree, since we visit each node once.
Space Complexity: O(1) - since we are modifying the tree in place and not using any additional data structures for storage.

Solution

To solve the problem, we can use a depth-first search (DFS) approach. The idea is to traverse the tree in a pre-order manner. During the traversal, we will reassign the left and right pointers of each node to create the linked list structure. Specifically, we will keep track of the previously visited node and set its right pointer to the current node and its left pointer to null.

Code Solutions

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def flatten(root: TreeNode) -> None:
    if not root:
        return
    
    # Initialize a pointer to the last visited node
    last_visited = None

    def dfs(node):
        nonlocal last_visited
        if not node:
            return
        
        # Visit the current node
        if last_visited:
            last_visited.right = node  # Set the right of last visited to current
            last_visited.left = None    # Set left to None
        
        last_visited = node  # Update last visited to current
        # Traverse the left subtree first, then the right
        dfs(node.left)
        dfs(node.right)

    dfs(root)
← Back to All Questions