114. Flatten Binary Tree to Linked List LeetCode Solution

In this guide, you will get 114. Flatten Binary Tree to Linked List LeetCode Solution with the best time and space complexity. The solution to Flatten Binary Tree to Linked List problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Problem Statement
Complexity Analysis
Flatten Binary Tree to Linked List solution in C++
Flatten Binary Tree to Linked List solution in Java
Flatten Binary Tree to Linked List solution in Python
Additional Resources

114. Flatten Binary Tree to Linked List LeetCode Solution image

Problem Statement of Flatten Binary Tree to Linked List

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]

Constraints:

The number of nodes in the tree is in the range [0, 2000].
-100 <= Node.val <= 100

Follow up: Can you flatten the tree in-place (with O(1) extra space)?

Complexity Analysis

Time Complexity: O(n)
Space Complexity: O(h)

114. Flatten Binary Tree to Linked List LeetCode Solution in C++

class Solution {
 public:
  void flatten(TreeNode* root) {
    if (root == nullptr)
      return;

    flatten(root->left);
    flatten(root->right);

    TreeNode* const left = root->left;    // flattened left
    TreeNode* const right = root->right;  // flattened right

    root->left = nullptr;
    root->right = left;

    // Connect the original right subtree to the end of the new right subtree.
    TreeNode* rightmost = root;
    while (rightmost->right != nullptr)
      rightmost = rightmost->right;
    rightmost->right = right;
  }
};
/* code provided by PROGIEZ */

114. Flatten Binary Tree to Linked List LeetCode Solution in Java

class Solution {
  public void flatten(TreeNode root) {
    if (root == null)
      return;

    flatten(root.left);
    flatten(root.right);

    TreeNode left = root.left;   // flattened left
    TreeNode right = root.right; // flattened right

    root.left = null;
    root.right = left;

    // Connect the original right subtree to the end of the new right subtree.
    TreeNode rightmost = root;
    while (rightmost.right != null)
      rightmost = rightmost.right;
    rightmost.right = right;
  }
}
// code provided by PROGIEZ

114. Flatten Binary Tree to Linked List LeetCode Solution in Python

class Solution:
  def flatten(self, root: TreeNode | None) -> None:
    if not root:
      return

    self.flatten(root.left)
    self.flatten(root.right)

    left = root.left  # flattened left
    right = root.right  # flattened right

    root.left = None
    root.right = left

    # Connect the original right subtree to the end of the new right subtree.
    rightmost = root
    while rightmost.right:
      rightmost = rightmost.right
    rightmost.right = right
 # code by PROGIEZ