flattening on Binary Tree

Question

Given a binary tree, flatten it into a linked list in-place following the same order as a pre-order traversal. The output should be the head of the linked list, where each node's left child is null and the right child points to the next node in the list.

Codemia · Accepted Answer

The problem at hand is to flatten a binary tree into a linked list following a pre-order traversal. The specific pattern here is a Depth-First Search (DFS) traversal, which is well-suited for this problem because we need to visit nodes in a specific order (root, left, right). This allows us to directly manipulate the pointers of each node as we traverse the tree, ensuring that the left child of each node is set to null and the right child points to the next node in the order of traversal.

We will use a recursive DFS approach to traverse the tree. The steps are as follows:
1. If the current node is null, return immediately.
2. Save the left and right children of the current node.
3. Set the left child of the current node to null.
4. If the left child exists, attach it to the right of the current node.
5. Move to the right child (which could be either the original right child or the saved left child).
6. Recursively call the function for the new right child.

For example, given the binary tree:
```
    1
   / \
  2   5
 / \   \
3   4   6
```
The pre-order traversal would be 1, 2, 3, 4, 5, 6. The resulting linked list would look like:
```
1 -> 2 -> 3 -> 4 -> 5 -> 6
```

Here is the Python implementation of the described approach:
```python
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

class Solution:
    def flatten(self, root: TreeNode) -> None:
        if not root:
            return
        # Flatten the left subtree
        self.flatten(root.left)
        # Flatten the right subtree
        self.flatten(root.right)
        # Store the left and right children
        left = root.left
        right = root.right
        
        # Set left to None
        root.left = None
        # Attach the left subtree to the right
        root.right = left
        # Find the end of the new right subtree
        current = root
        while current.right:
            current = current.right
        # Attach the original right subtree
        current.right = right
```
This function modifies the tree in-place and does not return anything.

The time complexity of this solution is O(n), where n is the number of nodes in the binary tree. This is because we visit each node exactly once during the DFS traversal. The space complexity is O(h), where h is the height of the tree, due to the recursion stack. In the worst case (for a skewed tree), this could be O(n), whereas for a balanced tree, it would be O(log n).

1. **Empty Tree**: If the input is None, the function should immediately return without any modification.
2. **Single Node Tree**: A tree with only one node should remain unchanged as it already satisfies the linked list structure.
3. **Left-Heavy or Right-Heavy Tree**: Ensure that trees that are skewed to one side are handled correctly, maintaining the order of traversal.
4. **Tree with only left children or only right children**: The function should still work as expected, preserving the pre-order traversal in the resulting linked list.

flattening on Binary Tree

DoorDash

What the Interviewer Expects

Key Topics to Cover

How to Approach This

Possible Follow-up Questions

Sharpen Your Skills on Codemia

Sample Answer

Problem Analysis

Approach

Submit Your Answer

DoorDash Software Engineer Interview Guide

Related Questions

Binary Search on graph

Count kth largest element in array

Find connected components in string

Merge Three Sorted strings

Binary Search on string