Flattening a Binary Tree to a Linked List

Introduction

Flattening a binary tree to a linked list is a common problem in data structures and algorithms. It involves transforming a binary tree into a structure that resembles a linked list, where each node has no left child and the right child points to the next node in the pre-order traversal.

Let's dive into this problem and explore an efficient solution using Java.

Problem Statement

Given a binary tree, flatten it into a linked list in-place. The "flattened" tree should use the right child pointers to link the nodes, and all left child pointers should be set to null.

For example, given the following binary tree:

    1
   / \
  2   5
 / \   \
3   4   6

The flattened tree should look like:

1
 \
  2
   \
    3
     \
      4
       \
        5
         \
          6

Approach

We'll use a pre-order traversal approach to flatten the tree. The key steps are:

1. Recursively flatten the left subtree
2. Recursively flatten the right subtree
3. Store the right child of the current node
4. Make the flattened left subtree the right child of the current node
5. Find the last node of the newly formed right subtree
6. Attach the stored right child to the end of this flattened subtree

Java Implementation

Let's implement this solution in Java:

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    
    TreeNode(int val) {
        this.val = val;
    }
}

class Solution {
    public void flatten(TreeNode root) {
        if (root == null) {
            return;
        }
        
        // Recursively flatten left and right subtrees
        flatten(root.left);
        flatten(root.right);
        
        // Store the right subtree
        TreeNode rightSubtree = root.right;
        
        // Make the flattened left subtree the right child
        root.right = root.left;
        root.left = null;
        
        // Find the end of the new right subtree
        TreeNode current = root;
        while (current.right != null) {
            current = current.right;
        }
        
        // Attach the original right subtree
        current.right = rightSubtree;
    }
}

Explanation

Let's break down the flatten method:

1. We first check if the root is null. If so, we return as there's nothing to flatten.

2. We recursively flatten the left and right subtrees. This ensures that all subtrees are flattened before we process the current node.

3. We store the right subtree in a variable rightSubtree. We'll need this later.

4. We make the flattened left subtree the new right child of the current node. This is a key step in the flattening process.

5. We set the left child to null, as per the problem requirements.

6. We then traverse to the end of this newly formed right subtree (which was originally the left subtree).

7. Finally, we attach the original right subtree (stored in rightSubtree) to the end of the current right subtree.

Time and Space Complexity

• Time Complexity: O(n), where n is the number of nodes in the tree. We visit each node once.
• Space Complexity: O(h), where h is the height of the tree. This space is used by the call stack during recursion.

Conclusion

Flattening a binary tree to a linked list is an interesting problem that combines tree traversal with in-place manipulation of the tree structure. By using a pre-order traversal approach, we can efficiently transform the tree while maintaining its original order.

This problem is a great example of how understanding tree structures and traversal techniques can be applied to solve complex transformation tasks. Practice implementing this solution to sharpen your skills with binary trees and recursive algorithms.