114. Flatten Binary Tree to Linked List

MediumStackTreeDepth-First SearchLinked ListBinary Tree

Problem Description

In this problem, we're asked to transform a given binary tree into a “flattened” linked list. The conditions for the flattened linked list are as follows:

We need to use the existing TreeNode class to represent the list nodes.
Each right child pointer of the TreeNode should point to the next node in the linked list.
The left child pointer of each TreeNode should be set to null, effectively removing the left children from all nodes.
The order of the nodes in the linked list must reflect the order of nodes visited in a pre-order traversal (visit the current node, then traverse left, then traverse right) of the binary tree.

The problem constraints are such that the tree needs to be modified in place, meaning no additional data structures should be created and the transformation has to use the existing tree nodes.

Flowchart Walkthrough

To determine the appropriate algorithm for solving LeetCode problem 114, "Flatten Binary Tree to Linked List," we'll use the Flowchart. Let's analyze this step by step:

Is it a graph?
- Yes: Although primarily about a binary tree, a tree is a special kind of graph.
Is it a tree?
- Yes: The problem explicitly mentions the flattened tree, confirming it's about a binary tree.
Use DFS
- Since it's confirmed as a tree, the immediate suggestion according to the flowchart is to use Depth-First Search (DFS). This is logical because the problem requires traversing the tree nodes in-depth to modify the tree's structure, essentially requiring each node to be visited and rearranged in a specific depth-first sequence.

Conclusion: The flowchart suggests using DFS for this tree transformation problem, guiding the rearrangement of nodes into a linked list format while preserving their original left-to-right depth-first order.

Intuition

To solve the problem, we need to understand that a pre-order traversal follows the root-left-right order. This guides us to the solution where we can repeatedly move the left subtree of a node so that it becomes the right subtree, while also ensuring that the original right subtree is not lost but appended after the moved left subtree.

Here's the intuition behind the solution step by step:

We start at the root of the binary tree and check if there's a left child.
If a left child is present, we find the right-most node of the left subtree (this will be the pre node mentioned in the code). This is where we will link the existing right subtree after we've moved the left subtree.
We then attach the current right subtree to the right-most node of the left subtree.
Now, we can safely move the left subtree to replace the right subtree (since we've already preserved the original right subtree).
We set the left child of the current node to null, effectively flattening this part of the tree.
We then move on to the next right child and repeat this process.
We continue this operation until we have visited all nodes and flattened the entire tree.

This in-place transformation is accomplished without the use of additional space (i.e., no extra list or tree is created), which is a requirement of this problem.

Learn more about Stack, Tree, Depth-First Search, Linked List and Binary Tree patterns.

Solution Approach

The solution implementation provided is an excellent example of in-place tree manipulation, which cleverly modifies the tree structure without the need for additional data structures. Here are the key elements of the implementation, expanded to clarify the process:

Loop Structure: The solution utilizes a while loop to iterate through the nodes of the tree. This loop continues until there are no more nodes to process, which is when root becomes None.
Left Subtree Processing: Inside the loop, the first step is to check if the current node (root) has a left child. If not, the tree is already flat from the current node, so the algorithm simply moves to the root.right.
Finding Right-Most Node: When a left child exists, we then need to find the right-most node of the left subtree. This part of the solution uses another while loop to traverse down to the bottom right of the subtree (while pre.right:). The right-most node is where the original right subtree will be appended after the left subtree is moved to the right.
Re-linking Subtrees: After finding the right-most node, the next step in the algorithm is to set its right child to the current root.right, which preserves the original right subtree (pre.right = root.right).
Flattening: Now that the right subtree has been saved, the entire left subtree is moved to the right side (root.right = root.left). This move aligns with the requirement that the right child pointer points to the next node in the list.
Eliminating Left Children: To comply with the flattened structure, the left child of the current node is set to None (root.left = None).
Advancing to the Next Node: Finally, with the left child processed and moved, the algorithm progresses to the next node by moving root to root.right.

By iteratively applying these steps to each node in the tree, starting from the root and advancing rightward, the binary tree is gradually transformed into a "linked list" that satisfies all given requirements.

The algorithm's foundation relies on tree traversal and careful reassignment of pointers, and the procedure harnesses the feature of the pre-order traversal pattern. Due to its in-place nature, the algorithm avoids using additional memory beyond a few pointers, and the entire tree is flattened with a space complexity of O(1) and time complexity of O(n), where n is the number of nodes in the binary tree.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's consider a simple binary tree and walk through the process of flattening it into a linked list using the solution approach described above.

Suppose we have the following binary tree:

Now, let's flatten this tree step-by-step:

Start at Root: We begin with the root node 1. It has a left child, which means we will need to find the right-most node of the left subtree.
Find Right-most Node of Left Subtree: The left child of 1 is 2, and it has a right child 4. We traverse to the right-most node of this left subtree, which is 4.
Re-linking Subtrees: We attach the right subtree of 1 (which starts with node 5) to the right pointer of node 4. Now node 4's right pointer points to node 5.

    1        4
   /          \
  2     =>     5
 / \            \
3   4            6

Flattening: We move the entire left subtree of 1 to the right. Now, the right child of 1 is 2, and the tree looks like this:

Eliminate Left Children: We set the left child of node 1 to null.
Advancing to Next Node: We now move to the right child of the root, which is 2. We repeat the process. Node 2 has a left child 3, but since 3 has no right child, it is already in the right place. We set the left child of node 2 to null.
Continue Flattening: Moving to node 4, we find no left child, so we continue to node 5. Node 5 has no left child but has a right child 6, which is already in the right place.

The tree is now a linked list:

We've completed the in-place transformation. Each step of the process either involved relinking or moving to the right child, and at no point did we use additional space. The original tree structure is efficiently re-purposed into a linked list following the pre-order traversal order.

Solution Implementation

1# Definition for a binary tree node.
2class TreeNode:
3    def __init__(self, val=0, left=None, right=None):
4        self.val = val
5        self.left = left
6        self.right = right
7
8class Solution:
9    def flatten(self, root: Optional[TreeNode]) -> None:
10        """
11        Flattens a binary tree to a linked list in place using the right child pointers.
12        The preorder traversal should be followed to flatten the tree.
13      
14        :param root: The root of the binary tree.
15        :return: None, the tree is modified in place.
16        """
17        # Iterate through each node of the binary tree
18        while root:
19            # If there is a left child, we need to rewire the connections according to
20            # the "flattened" preorder traversal
21            if root.left:
22                # Find the rightmost node of the left subtree
23                predecessor = root.left
24                while predecessor.right:
25                    predecessor = predecessor.right
26                # Connect the predecessor's right pointer to the current node's right child
27                predecessor.right = root.right
28                # The left child becomes the right child and the left child is set to None
29                root.right = root.left
30                root.left = None
31            # Move to the next right node (this could be the former left child of the current node)
32            root = root.right
33          
34        # The tree has now been converted to a linked list following the right child pointers.
35

1class Solution {
2  
3    // The method to flatten a binary tree to a linked list in-place.
4    public void flatten(TreeNode root) {
5        // Iterate until all the nodes are processed.
6        while (root != null) {
7            // If the current node has a left child, we need to process it.
8            if (root.left != null) {
9                // Find the rightmost node of the left subtree.
10                TreeNode rightmost = root.left;
11                while (rightmost.right != null) {
12                    rightmost = rightmost.right;
13                }
14                // Make the right of the rightmost node point to the root's right node.
15                rightmost.right = root.right;
16                // Move the left subtree to the right.
17                root.right = root.left;
18                // After moving the left subtree, set the left child to null.
19                root.left = null;
20            }
21            // Move on to the right child of the current node.
22            root = root.right;
23        }
24    }
25}
26
27/**
28 * Definition for a binary tree node.
29 * This is provided for completeness. Assume the TreeNode class is predefined elsewhere.
30 */
31class TreeNode {
32    int val;
33    TreeNode left;
34    TreeNode right;
35    // Constructor with no arguments initializes an empty node.
36    TreeNode() {}
37    // Constructor with a value initializes a node with the given value.
38    TreeNode(int val) { this.val = val; }
39    // Constructor with a value and two subtrees initializes a node with those values.
40    TreeNode(int val, TreeNode left, TreeNode right) {
41        this.val = val;
42        this.left = left;
43        this.right = right;
44    }
45}
46

1/**
2 * Definition for a binary tree node.
3 */
4struct TreeNode {
5    int val;
6    TreeNode *left;
7    TreeNode *right;
8    TreeNode() : val(0), left(nullptr), right(nullptr) {}
9    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
10    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
11};
12
13class Solution {
14public:
15    // Function to flatten a binary tree into a linked list in-place.
16    void flatten(TreeNode* root) {
17        // Continue flattening the tree until we have processed all nodes.
18        while (root) {
19            // Check if the current node has a left child.
20            if (root->left) {
21                // Find the rightmost node in the left subtree.
22                TreeNode* rightMost = root->left;
23                while (rightMost->right) {
24                    rightMost = rightMost->right;
25                }
26              
27                // Attach the right subtree of the current node to the rightmost node.
28                rightMost->right = root->right;
29
30                // Move the left subtree under the current node to the right.
31                root->right = root->left;
32
33                // Set the left child of the current node to nullptr.
34                root->left = nullptr;
35            }
36          
37            // Move on to the right child of the current node.
38            root = root->right;
39        }
40    }
41};
42

1// Definition for a binary tree node.
2class TreeNode {
3    val: number
4    left: TreeNode | null
5    right: TreeNode | null
6    constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
7        this.val = (val === undefined ? 0 : val);
8        this.left = (left === undefined ? null : left);
9        this.right = (right === undefined ? null : right);
10    }
11}
12
13/**
14 * Flattens a binary tree to a linked list in-place.
15 * @param {TreeNode | null} root - The root of the binary tree.
16 */
17function flatten(root: TreeNode | null): void {
18    // Iterate through the binary tree nodes.
19    while (root !== null) {
20        // If the current node has a left child...
21        if (root.left !== null) {
22            // Find the rightmost node of the left subtree.
23            let predecessor = root.left;
24            while (predecessor.right !== null) {
25                predecessor = predecessor.right;
26            }
27            // Connect right subtree of the current node to the rightmost node of the left subtree.
28            predecessor.right = root.right;
29          
30            // Move the left subtree to the right side and nullify the left pointer.
31            root.right = root.left;
32            root.left = null;
33        }
34        // Move to the next right node.
35        root = root.right;
36    }
37}
38

Time and Space Complexity

The above Python code implements a method to flatten a binary tree in-place along its pre-order traversal.

Time Complexity:

The time complexity of the algorithm is O(N), where N is the number of nodes in the tree. This is because each node is visited once. The inner while loop that finds the rightmost node of the left subtree does not add to the overall asymptotic complexity since it operates on nodes only once throughout the entire run of the algorithm. Each edge in the tree will be traversed at most twice: once when visiting the left child and once when attaching the left subtree to the right.

Space Complexity:

The space complexity of the algorithm is O(1) if we don't consider the recursive stack space used by the system for managing function calls. This is because no extra data structures are used; the tree is modified in place.

However, if we were to consider the recursive stack space (implicit stack space due to function calls), the space complexity would be O(H), where H is the height of the binary tree because the space used at any time is proportional to the depth of the recursion tree, which, in the worst case, is equal to the height of the binary tree. In a balanced tree, this would be O(log N), but in a skewed tree, it can be as bad as O(N) in the case of a degenerate tree (when the tree is like a linked list).

Learn more about how to find time and space complexity quickly using problem constraints.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

The three-steps of Depth First Search are:

Identify states;
Draw the state-space tree;
DFS on the state-space tree.

True

False

I don't know