flattening on Binary Tree

Question

Given a binary tree, flatten it into a linked list in-place such that the left child of each node is null and the right child points to the next node in the preorder traversal of the tree. The function should modify the tree structure directly and return nothing, with the output being the flattened linked list represented by the right pointers of the nodes.

Codemia · Accepted Answer

The problem requires us to flatten a binary tree into a linked list using the right pointers, specifically following a preorder traversal pattern (Node -> Left -> Right). The two-pointer technique does not directly apply here, but a recursive or iterative approach using a stack can help manage the tree's structure as we traverse it. We need to ensure that we modify the tree in-place, which means we cannot use additional data structures to store nodes permanently.

1. Start with the root of the binary tree. 
2. Use a recursive function that takes the current node as an argument. 
3. If the node is null, return. 
4. First, process the left subtree by calling the function recursively on the left child. 
5. Next, process the right subtree by calling the function recursively on the right child. 
6. After the left subtree is processed, connect the left child to the right child (i.e., `node.left` should be set to `null` and `node.right` should point to the previously flattened left subtree). 
7. Finally, navigate to the end of the new right subtree (which was the left subtree) and connect it to the previously processed right subtree.

For example, given the tree: 
```
    1
   / \
  2   5
 / \   \
3   4   6
```
The flattened result should be: 1 -> 2 -> 3 -> 4 -> 5 -> 6.

Here is the Python solution for the problem:
```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 and right subtrees
        self.flatten(root.left)
        self.flatten(root.right)
        
        # Store the left and right children
        left = root.left
        right = root.right
        
        # Set left to None
        root.left = None
        
        # Reattach left subtree to the right
        root.right = left
        
        # Find the end of the new right subtree and attach the original right subtree
        current = root
        while current.right:
            current = current.right
        current.right = right
```

The time complexity of this approach 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 flattening process. The space complexity is O(h), where h is the height of the tree, due to the recursion stack. In the worst case (a skewed tree), h can be n, leading to a space complexity of O(n), but in a balanced tree, it would be O(log n).

1. An empty tree (root is None): The function should simply return without doing anything. 
2. A tree with only one node: The result should remain the same as there are no children to flatten. 
3. A right-skewed tree (e.g., all nodes only have right children): The output should be the same as the input tree. 
4. A left-skewed tree (e.g., all nodes only have left children): The output should be a linked list that goes from the root to the last node in the left chain.

flattening on Binary Tree

Walmart

How to Approach This

Sharpen Your Skills on Codemia

Sample Answer

Problem Analysis

Approach

Submit Your Answer

Walmart 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