114. Flatten Binary Tree to Linked List

The "linked list" should be in the same order as a pre-order traversal of the binary tree.

Approach 1:

class Solution {
    private TreeNode prev = null;
    public void flatten(TreeNode root) {
        if (root == null)
            return;
        flatten(root.right);
        flatten(root.left);
        root.right = prev;
        root.left = null;
        prev = root;
    }
}
                

Time Complexity: O(n) and Space Complexity: O(n)

The problem Flatten Binary Tree to Linked List asks to flatten a binary tree into a linked list. The linked list should be in the same order as a pre-order traversal of the binary tree. This problem is interesting because it requires both tree traversal and restructuring of the tree into a different form.

Problem Statement

Given the root of a binary tree, flatten the tree into a "linked list" in place. The "linked list" should be a flattened binary tree such that:

• The left child of each node should be null.
• The right child of each node should point to the next node in the pre-order traversal of the tree.

Approach to Solve the Problem

The flattening process requires converting the binary tree into a linked list in a pre-order fashion. Pre-order traversal visits the root node first, followed by the left subtree, and then the right subtree.

To solve this, we can use a depth-first search (DFS) approach or a recursive approach. The idea is to maintain a pointer to the last visited node and attach the left subtree to the right child of the current node, then attach the right subtree. The key is to perform the tree restructuring in place, without using extra memory for another linked list structure.

Steps for the Flattening Process

1. Perform a pre-order traversal of the tree.
2. For each node, attach its left child to its right child.
3. Make the left child null for each node.
4. Recursively flatten the right subtree of each node.

Solution Implementation

Here is the Python implementation of the solution:

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):
        if not root:
            return
        
        # Helper function to flatten the tree
        def flattenTree(node):
            if not node:
                return None
            
            # Flatten the left subtree
            left = flattenTree(node.left)
            # Flatten the right subtree
            right = flattenTree(node.right)
            
            # If there is a left child, we move it to the right
            if left:
                node.right = left
                node.left = None
                
                # Find the rightmost node of the current right subtree
                while left.right:
                    left = left.right
                
                # Connect the original right subtree
                left.right = right
            
            return node
        
        flattenTree(root)
        

Here is the Java implementation of the solution:

public class Solution {
    public void flatten(TreeNode root) {
        if (root == null) {
            return;
        }
        
        // Helper function to flatten the tree
        flattenTree(root);
    }

    private TreeNode flattenTree(TreeNode node) {
        if (node == null) {
            return null;
        }

        TreeNode left = flattenTree(node.left);
        TreeNode right = flattenTree(node.right);

        if (left != null) {
            node.right = left;
            node.left = null;
            
            while (left.right != null) {
                left = left.right;
            }
            left.right = right;
        }

        return node;
    }
}
        

Example

Consider the following binary tree:

            Tree Structure:
                1
               / \
              2   5
             / \   \
            3   4   6
        

After flattening the tree, the structure would look like:

            Flattened Tree:
            1 -> 2 -> 3 -> 4 -> 5 -> 6
        

In the flattened tree, the left child of each node is null, and the right child of each node points to the next node in the pre-order traversal.

Complexity Analysis

Time Complexity: O(n), where n is the number of nodes in the tree. Each node is visited once during the pre-order traversal, and the process of restructuring the tree involves constant-time operations for each node.

Space Complexity: O(h), where h is the height of the tree. This is due to the recursion stack used in the depth-first traversal. In the worst case, the tree can be skewed, and the height would be O(n), resulting in O(n) space complexity.

Applications

• Converting a binary tree to a linked list is useful in scenarios where we need to process nodes in a sequential manner while maintaining a tree-like structure for traversal.
• Flattened trees can be used in problems where operations like preorder traversal need to be performed frequently on the same tree structure.
• This problem is an important exercise in recursion, tree manipulation, and space optimization.

Conclusion

The Flatten Binary Tree to Linked List problem is an excellent example of using tree traversal techniques to transform the structure of a binary tree into a linear form. By following a pre-order traversal and modifying the tree in place, we can achieve a flattened structure with constant space complexity. This problem teaches efficient tree manipulation and recursion techniques that are essential for many advanced algorithms and real-world applications.

Overall, flattening a binary tree into a linked list helps reinforce concepts related to tree traversal, recursion, and space optimization, which are fundamental in solving many complex problems involving trees and graphs.