Flatten Binary Tree to Linked List

Medium

Apple

2 views

Topics:

TreesRecursion

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.

For example:

Consider the following binary tree:

The flattened tree should be:

That is, the tree is transformed into a linked list by modifying the right pointers to point to the next node in the pre-order traversal, and the left pointers are set to null.

Here are a few test cases to consider:

Empty Tree: root = [] should result in [].
Single Node Tree: root = [0] should result in [0].
Balanced Tree: A balanced tree like the one shown above.
Left Skewed Tree: A tree where all nodes are left children.
Right Skewed Tree: A tree where all nodes are right children.

Write a function to flatten a given binary tree in-place.

Flatten Binary Tree to Linked List

Medium

Apple

2 views

Topics:

TreesRecursion

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.

For example:

Consider the following binary tree:

The flattened tree should be:

That is, the tree is transformed into a linked list by modifying the right pointers to point to the next node in the pre-order traversal, and the left pointers are set to null.

Here are a few test cases to consider:

Empty Tree: root = [] should result in [].
Single Node Tree: root = [0] should result in [0].
Balanced Tree: A balanced tree like the one shown above.
Left Skewed Tree: A tree where all nodes are left children.
Right Skewed Tree: A tree where all nodes are right children.

Write a function to flatten a given binary tree in-place.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the expected range of values in the binary tree nodes?
Could the root of the tree be null (empty tree)?
Is the input always a valid binary tree or should I handle cases where the input may not represent a valid tree?
Can I assume I can modify the tree nodes' left and right pointers directly, or do I need to create a new linked list?
Is there any particular behavior expected if the tree contains duplicate values?

Brute Force Solution

Approach

The brute force way to flatten a tree to a linked list involves exploring all possible tree traversals. We essentially try every possible order to line up the nodes. Finally, we pick one of those orders to become our linked list.

Here's how the algorithm would work step-by-step:

First, make a list of all the nodes in the tree by exploring all possible ways to walk through it. Think about starting at the top, then going left and right in different combinations to visit every node.
Now, consider every possible order you could arrange these nodes in. This means trying every single combination from the first node to the last.
For each of these orderings, imagine connecting the nodes one after another like a linked list, where each node points to the next one in the order.
Pick one of these orderings. Any ordering will work, so long as all of the nodes are linked together.

Code Implementation

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

def flatten_binary_tree_brute_force(root):
    all_nodes = []

    def get_all_nodes(node):
        if not node:
            return
        all_nodes.append(node)
        get_all_nodes(node.left)
        get_all_nodes(node.right)

    # Collect all nodes from the tree.
    get_all_nodes(root)

    import itertools
    
    # Attempt every possible permutation.
    for permutation in itertools.permutations(all_nodes):
        # We create a linked list based on a particular permutation.
        for i in range(len(permutation) - 1):
            permutation[i].left = None
            permutation[i].right = permutation[i+1]
        
        if permutation:
            permutation[-1].left = None
            permutation[-1].right = None

        if permutation:
            # Return the 'head' of the flattened list
            return permutation[0]

    return None

Big(O) Analysis

Time Complexity

O(n!) – The proposed brute force solution involves generating all possible traversals (permutations) of the n nodes in the binary tree. Generating all permutations of n elements takes O(n!) time. After generating each permutation, linking the nodes in that specific order would take O(n) time. However, the dominant factor is generating the permutations themselves, so the time complexity is O(n!) as it far outweighs the cost of constructing the linked list for each permutation. Therefore, the overall time complexity is O(n!).

Space Complexity

O(N!) – The brute force approach described first creates a list of all N nodes in the tree which initially contributes O(N) space. Then, it considers all possible orderings of these nodes, which amounts to N! permutations. For each of these N! orderings, the algorithm implicitly needs to store the current permutation being considered. Thus, the space complexity is driven by the need to store these permutations, leading to O(N!) space. This is because in the worst case, the algorithm could explore a significant fraction of all N! possible orderings before finding a suitable flattened linked list.

Optimal Solution

Approach

The goal is to rearrange the tree so it looks like a linked list, where each node's 'right' points to the next node in the list, and the 'left' child is always empty. The clever trick is to work from the bottom up, solving smaller subproblems first and connecting them as we move upwards.

Here's how the algorithm would work step-by-step:

Start by looking at the leaves (the very bottom nodes) of the tree.
For each node, remember what's on the right side of it, then rearrange so the left branch becomes the right branch, and the original right branch gets tacked on to the end of the new right branch.
Move upwards, repeating this process for each node. The key is the subtrees are already flattened, so it's easy to connect them.
Continue this until you reach the very top (the root). At the end, the entire tree will be straightened out into a linked list-like structure.

Code Implementation

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

def flatten_binary_tree(root):
    if not root:
        return None

    def flatten_subtree(node):
        if not node:
            return None

        left_subtree_tail = flatten_subtree(node.left)
        right_subtree_tail = flatten_subtree(node.right)

        # Store the right subtree before modification
        original_right_subtree = node.right

        # Move the left subtree to the right
        if node.left:
            node.right = node.left
            node.left = None

            # Connect tail of the left to original right
            if left_subtree_tail:
                left_subtree_tail.right = original_right_subtree

        # Find the tail of the flattened tree
        tail = right_subtree_tail if right_subtree_tail else left_subtree_tail if left_subtree_tail else node
        
        return tail

    flatten_subtree(root)

Big(O) Analysis

Time Complexity

O(n) – The algorithm visits each node in the binary tree exactly once. For each node, a constant amount of work is performed which involves rearranging pointers to flatten the subtree rooted at that node. Since there are n nodes in the tree and each node is visited only once with constant time operations, the time complexity is directly proportional to the number of nodes.

Space Complexity

O(N) – The provided explanation describes a recursive process operating on each node of the binary tree. This recursion creates stack frames. In the worst-case scenario, the tree might be skewed (like a linked list), resulting in a recursion depth proportional to the number of nodes, N. Therefore, the maximum auxiliary space required for the call stack is O(N).

Edge Cases

Case	How to Handle
Null root (empty tree)	The function should return immediately without any modification if the root is null.
Tree with only a root node	The root's left should be null and right should remain null (already flattened).
Tree with only a left child	The left child should become the right child, and the left child should be set to null.
Tree with only a right child	The right child should remain as the right child, and the left child should be set to null.
Skewed tree (all nodes on one side)	The algorithm should still flatten the tree correctly in preorder, regardless of skewness, by sequentially attaching nodes to the right.
Large tree (potential stack overflow with recursion)	Consider an iterative approach to avoid stack overflow errors with deep trees.
Tree with duplicate values	The preorder traversal based flattening works independently of node values, so duplicates do not affect the correctness.
Memory constraints with very large trees	In-place modification is crucial to adhere to memory constraints, and iterative implementations might offer better memory management.