algoadvance

Leetcode 114. Flatten Binary Tree to Linked List

Problem Statement

Given a binary tree, flatten it to a linked list in-place.

For example, given the following tree:

    1
   / \
  2   5
 / \   \
3   4   6

The flattened tree should look like:

1
 \
  2
   \
    3
     \
      4
       \
        5
         \
          6

Clarifying Questions

  1. In-Place Requirement: The problem specifies that the tree should be flattened in-place, meaning we should not use any additional data structures like arrays or lists to hold nodes temporarily.
  2. Node Structure: Assuming we are using the standard binary tree node structure as defined below: 
     struct TreeNode {
     int val;
     TreeNode *left;
     TreeNode *right;
     TreeNode() : val(0), left(nullptr), right(nullptr) {};
     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {};
     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {};
 };

Strategy

To flatten the binary tree into a linked list:

  1. Recursively Flatten the Left and Right Subtrees: First, recursively flatten the left and right subtrees.
  2. Reattach Nodes: If the left subtree exists:
    • Find the rightmost node of the left subtree.
    • Attach the right subtree to the rightmost node of the left subtree.
    • Move the entire left subtree to the right subtree and set the left subtree to nullptr.
  3. Iterate Approach: Alternatively, you can use an iterative approach using a stack to avoid recursion.

Both recursive and iterative methods will be discussed, but let’s proceed with the recursive implementation.

Code

Here is the C++ code for the recursive solution:

class Solution {
public:
    void flatten(TreeNode* root) {
        // Base case: if the tree is empty or it is a leaf node, return
        if (root == nullptr || (root->left == nullptr && root->right == nullptr)) {
            return;
        }
        
        // Flatten the left subtree
        if (root->left != nullptr) {
            flatten(root->left);
            
            // Temporarily store the right subtree
            TreeNode* tempRight = root->right;
            
            // Move the left subtree to the right
            root->right = root->left;
            root->left = nullptr;
            
            // Find the rightmost node of the moved subtree
            TreeNode* t = root->right;
            while (t->right != nullptr) {
                t = t->right;
            }
            
            // Attach the temporarily stored right subtree
            t->right = tempRight;
        }
        
        // Flatten the right subtree
        flatten(root->right);
    }
};

Time Complexity

The time complexity of this solution is O(n), where n is the number of nodes in the tree. This is because each node is visited once during the traversal in the recursive calls.

The space complexity is O(h) where h is the height of the tree, which corresponds to the space used by the system’s call stack during the recursive calls. In the worst case, for a completely unbalanced tree, this can be O(n), but on average for a balanced tree, it would be O(log n).

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI