algoadvance

Leetcode 114. Flatten Binary Tree to Linked List

Problem Statement

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.

Example:

Input: root = [1, 2, 5, 3, 4, null, 6]
Output: [1, null, 2, null, 3, null, 4, null, 5, null, 6]

Clarifying Questions

1. What do we do if the tree is empty (i.e., root is null)?
   • If the tree is empty, the output should also be an empty list.
2. Are there any constraints on the values of the nodes?
   • No, node values can be any integer.
3. Do we need to handle any edge cases specifically, like a tree with only one node?
   • Yes, for a single node tree, the output should be the single node itself with its left pointer as null.

Strategy

1. The key to solving this problem is to simulate the process of pre-order traversal (root-left-right) and at the same time, re-link the nodes to form a single right-skewed tree.
2. We can use a modified Depth-First Search (DFS) to flatten the tree:
   • Recurse to the right subtree and keep track of the “tail” (the last node in the flattened right subtree).
   • Recurse to the left subtree and attach it to the right of the current node.
   • Link the flattened right subtree to the end of the newly attached left subtree.
3. This approach uses recursion and modifies the tree during traversal, which provides an efficient way to solve the problem.

Code

public class Solution {
    public void flatten(TreeNode root) {
        flattenTree(root);
    }

    private TreeNode flattenTree(TreeNode node) {
        // Base case: if the node is null, return null
        if (node == null) return null;

        // If the node is a leaf, return the node itself
        if (node.left == null && node.right == null) return node;

        // Recursively flatten the left and right subtrees
        TreeNode leftTail = flattenTree(node.left);
        TreeNode rightTail = flattenTree(node.right);

        // If there was a left subtree, we shuffle the connections
        if (leftTail != null) {
            leftTail.right = node.right;
            node.right = node.left;
            node.left = null;
        }

        // The new tail is the rightmost of the right subtree
        return rightTail != null ? rightTail : leftTail;
    }
}

Time Complexity

• The algorithm visits each node once, performing constant time operations for re-linking nodes during each visit.
• Therefore, the time complexity of this solution is O(n), where n is the number of nodes in the binary tree.

Space Complexity

• The space complexity is O(h), where h is the height of the tree, due to the recursion stack. In the worst case (unbalanced tree), this can be O(n), but for a balanced tree, it would be O(log n).

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

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?