Last updated on January 21st, 2025 at 02:16 am

Here, we see a Flatten Binary Tree to Linked List LeetCode Solution. This Leetcode problem is solved using different approaches in many programming languages, such as C++, Java, JavaScript, Python, etc.

List of all LeetCode Solution

Topics

Math

Companies

Indeed

Level of Question

Medium

Flatten Binary Tree to Linked List LeetCode Solution

1. 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 1:

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

Example 2:
Input: root = []
Output: []

Example 3:
Input: root = [0]
Output: [0]

2. Coding Pattern Used in Solution

The coding pattern used in this code is “Tree Depth First Search (DFS)”. The code traverses the binary tree in a depth-first manner, modifying the tree in-place to flatten it into a linked list-like structure. The traversal involves recursive or iterative exploration of the left and right subtrees.

3. Code Implementation in Different Languages

3.1 Flatten Binary Tree to Linked List C++

class Solution {
public:
    void flatten(TreeNode* root) {
        if( root )
        {
            TreeNode* temp = root->right;
            root->right = root->left;
            root->left = nullptr;
            TreeNode* node = root;
            while( node->right )
            {
                node = node->right;
            }
            node->right = temp;
            flatten( root->right ); 
        } 
        return;      
    }
};

3.2 Flatten Binary Tree to Linked List Java

class Solution {
    public void flatten(TreeNode root) {
        if (root == null) return;
        TreeNode left = root.left;
        TreeNode right = root.right;
        root.left = null;
        flatten(left);
        flatten(right);
        root.right = left;
        TreeNode cur = root;
        while (cur.right != null) cur = cur.right;
        cur.right = right;        
    }
}

3.3 Flatten Binary Tree to Linked List JavaScript

var flatten = function(root) {
    let curr = root
    while (curr) {
        if (curr.left) {
            let runner = curr.left
            while (runner.right) runner = runner.right
            runner.right = curr.right, curr.right = curr.left, curr.left = null
        }
        curr = curr.right
    }
};

3.4 Flatten Binary Tree to Linked List Python

class Solution(object):
    def flatten(self, root):
        curr = root
        while curr:
            if curr.left:
                runner = curr.left
                while runner.right: runner = runner.right
                runner.right, curr.right, curr.left = curr.right, curr.left, None
            curr = curr.right

4. Time and Space Complexity

	Time Complexity	Space Complexity
C++	O(n²)	O(n)
Java	O(n²)	O(n)
JavaScript	O(n²)	O(1)
Python	O(n²)	O(1)

The recursive implementations (C++ and Java) use additional space for the recursion stack, while the iterative implementations (JavaScript and Python) are more space-efficient.
The time complexity is (O(n^2)) in all cases due to the repeated traversal of the rightmost path of the left subtree for each node.
The in-place modification of the tree ensures no additional memory is used for storing the flattened tree.