114. Flatten Binary Tree to Linked List
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
TreeNodeclass to represent the list nodes. - Each
rightchild pointer of theTreeNodeshould point to the next node in the linked list. - The
leftchild pointer of eachTreeNodeshould be set tonull, 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.
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.
Which algorithm should you use to find a node that is close to the root of the tree?
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
whileloop to iterate through the nodes of the tree. This loop continues until there are no more nodes to process, which is whenrootbecomesNone. -
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 theroot.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
whileloop 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
rightchild to the currentroot.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 therightchild 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
roottoroot.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.
Which two pointer technique does Quick Sort use?
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:
1 1 2 / \ 3 2 5 4 / \ \ 53 4 6
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
1is2, and it has a right child4. We traverse to the right-most node of this left subtree, which is4. -
Re-linking Subtrees: We attach the right subtree of
1(which starts with node5) to the right pointer of node4. Now node4's right pointer points to node5.
1 1 4 2 / \ 3 2 => 5 4 / \ \ 53 4 6
- Flattening: We move the entire left subtree of
1to the right. Now, the right child of1is2, and the tree looks like this:
11 2 \ 3 2 4 / \ 53 4 6 \ 7 5 8 \ 9 6
-
Eliminate Left Children: We set the left child of node
1tonull. -
Advancing to Next Node: We now move to the right child of the root, which is
2. We repeat the process. Node2has a left child3, but since3has no right child, it is already in the right place. We set the left child of node2tonull. -
Continue Flattening: Moving to node
4, we find no left child, so we continue to node5. Node5has no left child but has a right child6, which is already in the right place.
The tree is now a linked list:
11 2 \ 3 2 4 \ 5 3 6 \ 7 4 8 \ 9 5 10 \ 11 6
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.
351class 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}
461/**
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};
421// 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}
38Which of these properties could exist for a graph but not a tree?
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.
Depth first search is equivalent to which of the tree traversal order?
Recommended Readings
Stack Intro Imagine you have a pile of books on your desk If you want to add a new book you place it on top If you want to read a book you take it from the top And if you simply want to see which book is on the top you
Everything About Trees A tree is a type of graph data structure composed of nodes and edges Its main properties are It is acyclic doesn't contain any cycles There exists a path from the root to any node Has N 1 edges where N is the number of nodes in the tree and
https algomonster s3 us east 2 amazonaws com cover_photos dfs svg Depth First Search Prereqs Recursion Review problems recursion_intro Trees problems tree_intro With a solid understanding of recursion under our belts we are now ready to tackle one of the most useful techniques in coding interviews Depth First Search DFS
Got a question?ย Ask the Teaching Assistantย anything you don't understand.
Still not clear? Ask in the Forum, ย Discordย orย Submitย the part you don't understand to our editors.