Last updated on July 19th, 2024 at 11:32 pm

Here, We see Flatten Binary Tree to Linked List LeetCode Solution. This Leetcode problem is done in many programming languages like C++, Java, JavaScript, Python, etc. with different approaches.

List of all LeetCode Solution

Topics

Math

Companies

Indeed

Level of Question

Medium

Flatten Binary Tree to Linked List LeetCode Solution

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]

1. Flatten Binary Tree to Linked List Leetcode Solution 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;      
    }
};

2. Flatten Binary Tree to Linked List Leetcode Solution 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. Flatten Binary Tree to Linked List Solution 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
    }
};

4. Flatten Binary Tree to Linked List Solution 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