Why must every left pointer be set to null?

The flattened structure behaves like a singly linked list using only right pointers. Leaving left pointers unchanged would preserve branches from the original tree.

Why is the right subtree processed before the left subtree in the recursive approach?

The flattened structure is built backward. Processing Right → Left → Root ensures that previous always represents the node that should immediately follow the current node in normal preorder order.

Why is the original right subtree attached to the rightmost node of the left subtree?

Preorder visits the complete left subtree before entering the right subtree. After rewiring, the rightmost node of the moved left subtree becomes the point from which traversal should continue into the original right subtree.

Does flattening create new tree nodes?

No. The original nodes are reused, and only their left and right pointers are modified.

Which approach is generally preferred in interviews?

Reverse-preorder DFS is concise and uses only O(H) recursion space. When constant auxiliary space is specifically required, the iterative pointer-rewiring approach achieves O(N) time and O(1) extra space.

Flatten Binary Tree to Linked List

Given the root of a binary tree, modify the tree in-place so that it becomes a linked-list-like structure following the tree's preorder traversal.

After flattening:

Every node's left pointer must be null.
Every node's right pointer must point to the next node in preorder.
The original TreeNode structure must be reused.

Return the root of the flattened tree.

Example 1

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

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

Explanation:
The preorder traversal of the original tree is 1 -> 2 -> 3 -> 4 -> 5 -> 6. After flattening, every left pointer becomes null, while the right pointers connect the nodes in this preorder sequence.

Example 2

Input:
root = [1, 2, 3]

Output:
[1, null, 2, null, 3]

Explanation:
The preorder traversal is 1 -> 2 -> 3, so the flattened tree contains the same sequence connected only through right pointers.

Practice it by yourself before moving onto the solutionTry now

Approach 1

The flattened tree must follow exactly the same order as a preorder traversal:

Root → Left → Right

A straightforward approach is to first perform preorder traversal and store references to all visited nodes in a list. Once traversal is completed, the required ordering is already available.

The stored nodes can then be reconnected so that every node points to the next node through its right pointer, while its left pointer is cleared.

This keeps traversal and pointer modification separate, which makes the approach simple to understand, but storing all nodes requires additional linear space.

Algorithm

A preorder traversal is performed, and every visited node is stored in a list because preorder gives exactly the order required in the flattened tree.
After traversal has been completed, consecutive nodes in the stored list are processed.
For each node except the last one, its left pointer is set to null because the flattened structure must not contain left links.
Its right pointer is connected to the next node in the preorder list so that the required sequence is preserved.
For the final node, both child pointers are adjusted so that it becomes the end of the flattened structure.
After all links have been rearranged, the original root is returned.

Dry Run

Flatten Binary Tree Appraoch 1 Dry Run .png

Solution

1#include <bits/stdc++.h>
2using namespace std;
3
4struct TreeNode {
5    int val;
6    TreeNode* left;
7    TreeNode* right;
8
9    TreeNode(int value) {
10        val = value;
11        left = nullptr;
12        right = nullptr;
13    }
14};
15
16class Solution {
17private:
18    // Stores nodes in the exact preorder
19    // required by the flattened tree.
20    void preorder(
21        TreeNode* root,
22        vector<TreeNode*>& nodes
23    ) {
24        if (root == nullptr) {
25            return;
26        }
27
28        nodes.push_back(root);
29
30        preorder(root->left, nodes);
31        preorder(root->right, nodes);
32    }
33
34public:
35    // Reconnects preorder nodes into
36    // one right-linked chain.
37    TreeNode* flatten(TreeNode* root) {
38        if (root == nullptr) {
39            return nullptr;
40        }
41
42        vector<TreeNode*> nodes;
43
44        preorder(root, nodes);
45
46        // Consecutive preorder nodes are linked
47        // through right pointers only.
48        for (int i = 0; i < nodes.size() - 1; i++) {
49            nodes[i]->left = nullptr;
50            nodes[i]->right = nodes[i + 1];
51        }
52
53        // The final node terminates
54        // the flattened structure.
55        nodes.back()->left = nullptr;
56        nodes.back()->right = nullptr;
57
58        return root;
59    }
60};
61
62int main() {
63    TreeNode* root = new TreeNode(1);
64    root->left = new TreeNode(2);
65    root->right = new TreeNode(5);
66    root->left->left = new TreeNode(3);
67    root->left->right = new TreeNode(4);
68    root->right->right = new TreeNode(6);
69
70    Solution solution;
71    root = solution.flatten(root);
72
73    while (root != nullptr) {
74        cout << root->val << " ";
75        root = root->right;
76    }
77
78    return 0;
79}

Complexity Analysis

Let N be the number of nodes in the binary tree and H be the height of the tree.

Time Complexity: O(N), where N is the number of nodes in the binary tree. Every node is visited once during preorder traversal and processed once more while the stored nodes are reconnected.

Space Complexity: O(N), where N is the number of nodes stored in the preorder list. The recursive traversal may additionally require up to O(H) stack space, where H is the height of the binary tree.

Approach 2

Storing the complete preorder traversal can be avoided by creating the required links while recursion returns.

The desired flattened order is:

Root → Left → Right

If the tree is processed in the reverse order:

Right → Left → Root

a pointer named previous can be maintained. The name represents the node that should appear immediately after the current node in the final flattened preorder sequence.

Once both subtrees have been processed, the current node can be connected directly to previous.

The following updates are performed:

current.right = previous

current.left = null

previous = current

In this way, the flattened structure is built backward while only the recursion stack is required.

Algorithm

A pointer named previous is maintained to represent the node that should immediately follow the current node in the final flattened preorder sequence.
The right subtree is processed before the left subtree because the flattened list is being constructed in reverse preorder order.
After both recursive calls have been completed, the current node's right pointer is connected to previous.
The current node's left pointer is set to null because no left links are allowed in the flattened structure.
previous is updated to the current node so that the next ancestor processed during recursion can be connected to it.
Once the root has been processed, the complete preorder-linked structure has been formed.

Dry Run

Flatten Binary Tree Appraoch 2 Dry Run .png

Solution

1#include <bits/stdc++.h>
2using namespace std;
3
4struct TreeNode {
5    int val;
6    TreeNode* left;
7    TreeNode* right;
8
9    TreeNode(int value) {
10        val = value;
11        left = nullptr;
12        right = nullptr;
13    }
14};
15
16class Solution {
17private:
18    TreeNode* previous;
19
20    // Processes nodes in reverse preorder so
21    // previous is always the next flattened node.
22    void reversePreorder(TreeNode* root) {
23        if (root == nullptr) {
24            return;
25        }
26
27        reversePreorder(root->right);
28        reversePreorder(root->left);
29
30        // previous is the node that must follow
31        // the current node in normal preorder.
32        root->right = previous;
33        root->left = nullptr;
34
35        previous = root;
36    }
37
38public:
39    // Flattens the tree using reverse
40    // preorder and recursion.
41    TreeNode* flatten(TreeNode* root) {
42        previous = nullptr;
43
44        reversePreorder(root);
45
46        return root;
47    }
48};
49
50int main() {
51    TreeNode* root = new TreeNode(1);
52    root->left = new TreeNode(2);
53    root->right = new TreeNode(5);
54    root->left->left = new TreeNode(3);
55    root->left->right = new TreeNode(4);
56    root->right->right = new TreeNode(6);
57
58    Solution solution;
59    root = solution.flatten(root);
60
61    while (root != nullptr) {
62        cout << root->val << " ";
63        root = root->right;
64    }
65
66    return 0;
67}

Complexity Analysis

Let N be the number of nodes in the binary tree and H be the height of the tree.

Time Complexity: O(N), where N is the number of nodes in the binary tree. Every node is processed exactly once.

Space Complexity: O(H), where H is the height of the binary tree, due to the recursion stack. This becomes O(N) for a skewed tree and O(log N) for a balanced tree.

Approach 3

The tree can also be flattened without storing nodes and without using recursion.

A pointer named current is used to represent the node whose links are currently being rearranged.

Whenever current has a left subtree, preorder traversal requires the entire left subtree to appear before the original right subtree:

current → left subtree → right subtree

Therefore, the left subtree must be moved to current.right.

Before this can be done, the original right subtree must be preserved. A pointer can be moved to the rightmost node of the left subtree. This node is important because after the left subtree has been rewired into the right chain, it becomes the final node visited before preorder should continue into the original right subtree.

The original right subtree is therefore attached to this rightmost node. The left subtree is then shifted to the right, and current.left is cleared.

The process continues by moving current through the newly formed right pointers.

Algorithm

A pointer named current is initialized with the root so that the tree can be processed directly through its existing links.
While current is not null, its local subtree structure is examined.
If no left child exists, no rewiring is required at that node, and current is advanced to its right child.
If a left subtree exists, its rightmost node is located because that node must connect to the original right subtree after the left subtree is moved.
The original current.right subtree is attached to the right pointer of this rightmost node so that it is not lost.
The left subtree is moved to current.right, and current.left is set to null, placing the former left subtree immediately after the current node in preorder.
current is then advanced through its right pointer, and the process is continued until every node has been rewired.

Dry Run

Flatten Binary Tree Appraoch 3 Dry Run .png

Solution

1#include <bits/stdc++.h>
2using namespace std;
3
4struct TreeNode {
5    int val;
6    TreeNode* left;
7    TreeNode* right;
8
9    TreeNode(int value) {
10        val = value;
11        left = nullptr;
12        right = nullptr;
13    }
14};
15
16class Solution {
17public:
18    // Rewires the tree directly into preorder
19    // using constant auxiliary space.
20    TreeNode* flatten(TreeNode* root) {
21        TreeNode* current = root;
22
23        while (current != nullptr) {
24
25            if (current->left != nullptr) {
26                TreeNode* rightmost =
27                    current->left;
28
29                // The rightmost node of the left subtree
30                // must precede the original right subtree.
31                while (rightmost->right != nullptr) {
32                    rightmost = rightmost->right;
33                }
34
35                // The original right subtree is preserved
36                // after the complete left subtree.
37                rightmost->right =
38                    current->right;
39
40                // The left subtree is moved to the right
41                // because preorder visits it next.
42                current->right =
43                    current->left;
44
45                current->left = nullptr;
46            }
47
48            current = current->right;
49        }
50
51        return root;
52    }
53};
54
55int main() {
56    TreeNode* root = new TreeNode(1);
57    root->left = new TreeNode(2);
58    root->right = new TreeNode(5);
59    root->left->left = new TreeNode(3);
60    root->left->right = new TreeNode(4);
61    root->right->right = new TreeNode(6);
62
63    Solution solution;
64    root = solution.flatten(root);
65
66    while (root != nullptr) {
67        cout << root->val << " ";
68        root = root->right;
69    }
70
71    return 0;
72}

Complexity Analysis

Let N be the number of nodes in the binary tree.

Time Complexity: O(N), where N is the number of nodes in the binary tree. Although rightmost nodes of left subtrees are searched during rewiring, the traversal and pointer rearrangements together remain linear over the complete tree.

Space Complexity: O(1), because the tree is modified in-place using only a constant number of pointers such as current and the rightmost-node pointer.

Interview follow-up Questions

The nodes appear in the tree's preorder traversal order: root first, followed by the left subtree and then the right subtree.

Flatten Binary Tree to Linked List

Example 1

Example 2

Approach 1

Algorithm

Dry Run

Solution

Complexity Analysis

Approach 2

Algorithm

Dry Run

Solution

Complexity Analysis

Approach 3

Algorithm

Dry Run

Solution

Complexity Analysis

Interview follow-up Questions

Read Similar Blogs

Parent and Distance - Introduction

Check If a Binary Tree Is a Subtree of Another Tree

Count Nodes in a Complete Binary Tree

Flatten Binary Tree to Linked List

Example 1

Example 2

Approach 1

Algorithm

Dry Run

Solution

Complexity Analysis

Approach 2

Algorithm

Dry Run

Solution

Complexity Analysis

Approach 3

Algorithm

Dry Run

Solution

Complexity Analysis

Interview follow-up Questions

In what order do nodes appear after flattening?

Why must every left pointer be set to null?

Why is the right subtree processed before the left subtree in the recursive approach?

Why is the original right subtree attached to the rightmost node of the left subtree?

Does flattening create new tree nodes?

Which approach is generally preferred in interviews?

Read Similar Blogs

Parent and Distance - Introduction

Check If a Binary Tree Is a Subtree of Another Tree

Count Nodes in a Complete Binary Tree