algoadvance

You are 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 None.
• The “linked list” should be in the same order as a pre-order traversal of the binary tree.

Example:

Input: root = [1,2,5,3,4,null,6]
Output: [1,null,2,null,3,null,4,null,5,null,6]

Clarifying Questions

1. What’s the definition of the TreeNode class?

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

2. Can the input tree be empty?

   Yes, the root can be None.

3. Should we preserve the original tree structure?

   No, the tree structure will be modified to be in a linked-list format.

Strategy

We’ll use an iterative approach to flatten the tree:

1. Start from the root node.
2. Move through the nodes, always linking the right pointer of the current node to the next node in pre-order traversal.
3. If the current node has a left child:
   • Find the right-most node of the left subtree.
   • Link the right subtree of the current node to the right-most node.
   • Move the left subtree to the right and set the left child to None.
4. Move to the next node on the right and repeat.

Code

Here’s the implementation:

# 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):
    if not root:
        return

    current = root
    while current:
        if current.left:
            # Find the right-most node of the left subtree
            rightmost = current.left
            while rightmost.right:
                rightmost = rightmost.right
            
            # Connect the right subtree of the current node
            # to the rightmost node of the left subtree
            rightmost.right = current.right
            
            # Move the left subtree to the right and set left to None
            current.right = current.left
            current.left = None
        
        # Move on to the right node
        current = current.right

Time Complexity

The time complexity is (O(n)), where (n) is the number of nodes in the tree. Each node is visited once during the flattening process.

The space complexity is (O(1)) if we ignore the recursion stack, as the transformation is done in-place.

This should adequately flatten the binary tree as required.

Try our interview co-pilot at AlgoAdvance.com

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?