Flatten Binary Tree to LinkedList

Problem Overview

The "Flatten Binary Tree to Linked List" problem involves transforming a given binary tree into a linked list in-place, where the linked list follows the same depth-first preorder traversal of the original tree.

Problem Statement

Given a binary tree, flatten it into a linked list in-place. The linked list will have all the right child pointers forming a single path, representing the preorder traversal of the tree nodes. Importantly, the left child pointers of all nodes should be null, and the right child pointer of one node should point to the next node in the preorder sequence.

For reference, consider the following visual representation:

Example:
    1
   / \
  2   5
 / \   \
3   4   6

Transforms to:
1
 \
  2
   \
    3
     \
      4
       \
        5
         \
          6

Understanding the Problem

The problem is to convert a binary tree into a linked list (resembling a flattened structure) by reusing the tree's nodes and pointers. The process should follow a preorder traversal:

• Preorder Traversal: Visit the root node first, then recursively the left subtree, and finally the right subtree.

The essence is to intertwine the nodes to form a right-skewed linked list, as shown in the example above.

Key DSA Concepts and Theory

Before jumping into the solution, let's review some key concepts:

Binary Tree

A binary tree is a tree data structure where each node has at most two children, referred to as the left and right child. Binary trees are used in various applications like expression parsing, sorting, and routing algorithms.

Preorder Traversal

In preorder traversal, the nodes are recursively visited in this order:

1. Visit the root node.
2. Traverse the left subtree.
3. Traverse the right subtree.

Linked List

A linked list is a linear data structure composed of nodes where each node includes a data field and a reference (or pointer) to the next node in the sequence.

Solution Approach

The solution involves tree manipulation to ensure that all nodes are connected using right pointers following the preorder sequence. There are several ways to flatten the tree, but here's a common recursive approach:

Step-by-Step Solution

Method: Recursive Depth-First Search (DFS)

1. Base Case:

   • If the root is null, return immediately as there's nothing to flatten.

2. Recursive Flattening:

   • Recursively flatten the left subtree.
   • Recursively flatten the right subtree.

3. Reconstruction:

   • Save the original right subtree.
   • Move the left subtree to the right (since this is a right-skewed linked list, left should be null).
   • Traverse to the end of the newly reassigned right subtree and connect the saved original right subtree.

Here's how you can implement this in C++ and Java:

C++ Code

class Solution {
public:
    void flatten(TreeNode* root) {
        if (!root) return;
        
        // Flatten the left and right subtrees
        flatten(root->left);
        flatten(root->right);

        // Save the right subtree
        TreeNode* tempRight = root->right;
        
        // Move the left subtree to the right
        root->right = root->left;
        root->left = nullptr;

        // Go to the end of current right and connect it to the saved right subtree
        TreeNode* current = root;
        while (current->right) {
            current = current->right;
        }
        
        current->right = tempRight;
    }
};

Java Code

class Solution {
    public void flatten(TreeNode root) {
        if (root == null) return;

        // Flatten the left and right subtrees
        flatten(root.left);
        flatten(root.right);

        // Save the right subtree
        TreeNode tempRight = root.right;

        // Move the left subtree to the right
        root.right = root.left;
        root.left = null;

        // Go to the end of current right and connect it to the saved right subtree
        TreeNode current = root;
        while (current.right != null) {
            current = current.right;
        }

        current.right = tempRight;
    }
}

Time and Space Complexity Analysis

Time Complexity

• O(N), where N is the number of nodes in the tree. Each node is visited once to rebuild the links.

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 (unbalanced tree), this can approach O(N). In the average case (balanced tree), it is O(log N).

Common Mistakes to Avoid

• Forgetting to set the left pointer to null for every node in the resultant linked list.
• Incorrectly handling the subtree connections post reconstruction.
• Assuming the tree is a perfect binary tree, hence not accounting for edge cases.

Similar Problems on LeetCode

1. LeetCode 114: Flatten Binary Tree to Linked List - similar problem for further practice.
2. LeetCode 1008: Construct Binary Search Tree from Preorder Traversal

Additional Resources and References

1. Binary Tree Traversals (GeeksforGeeks)
2. Data Structures and Algorithm Analysis in Java by Mark Allen Weiss
3. Introduction to Algorithms by Thomas H. Cormen

Understanding this problem requires a strong grasp of tree manipulations and traversals. Practicing other tree-related problems can help reinforce these concepts.