What is the time complexity of Flatten Binary Tree to Linked List?

The optimal solution has a time complexity of O(n).

What data structures are used to solve Flatten Binary Tree to Linked List?

This problem uses Linked List, Stack, Tree, Depth-First Search, Binary Tree. Understanding these concepts is essential for solving this Medium problem efficiently.

What are the key insights for solving Flatten Binary Tree to Linked List?

Insight 1: The key is to perform a pre-order traversal while restructuring the tree. The pre-order traversal order is Node -> Left -> Right. Insight 2: We can use an iterative approach with O(1) space complexity, avoiding recursion's call stack overhead.

Which companies ask LeetCode 114. Flatten Binary Tree to Linked List in interviews?

This problem is frequently asked at Anduril, Apple, Google, Media.net, Myntra and 4 more companies.

JavaScript is required for the full interactive experience. However, all content is accessible without JavaScript.

Flatten Binary Tree to Linked List - LeetCode 114 Solution

Flatten Binary Tree to Linked List - Complete Solution Guide

Flatten Binary Tree to Linked List is LeetCode problem 114, a Medium level challenge. This complete guide provides step-by-step explanations, multiple solution approaches, and optimized code in python3, java, cpp, c.

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] Con

Detailed Explanation

The problem asks us to flatten a given binary tree into a linked list structure. The linked list should be formed by performing a pre-order traversal of the binary tree. Importantly, the left child of each node in the linked list must be NULL, and the right child must point to the next node in the pre-order traversal. We need to modify the tree in-place, meaning we shouldn't create a new tree structure but rather rearrange the existing one.

Solution Approach

The solution uses an iterative approach to flatten the binary tree in-place. It iterates through the tree, and when it encounters a node with a left child, it finds the rightmost node in the left subtree. It then reattaches the original right subtree of the current node to the rightmost node of the left subtree. The left subtree of the current node is then moved to become the new right subtree, and the left child of the current node is set to null. This process effectively transforms the tree into a linked list representation in pre-order.

Step-by-Step Algorithm

Step 1: Initialize a `current` pointer to the root of the tree.
Step 2: While `current` is not null, continue the iteration.
Step 3: If `current` has a left child:
Step 4: Find the rightmost node (`predecessor`) in the left subtree of `current`.
Step 5: Set the `right` child of `predecessor` to the `right` child of `current`.
Step 6: Set the `right` child of `current` to its `left` child.
Step 7: Set the `left` child of `current` to null.
Step 8: Move `current` to its `right` child, and repeat from Step 2.

Key Insights

Insight 1: The key is to perform a pre-order traversal while restructuring the tree. The pre-order traversal order is Node -> Left -> Right.
Insight 2: We can use an iterative approach with O(1) space complexity, avoiding recursion's call stack overhead.
Insight 3: For each node, find the rightmost node of its left subtree. Connect this rightmost node to the current node's right subtree. Then move the left subtree to the right, and set the left to null.

Complexity Analysis

Time Complexity: O(n)

Space Complexity: O(1)

Topics

This problem involves: Linked List, Stack, Tree, Depth-First Search, Binary Tree.

Companies

Asked at: Anduril, Apple, Google, Media.net, Myntra, PayPal, Salesforce, Uber, Yahoo.

Flatten Binary Tree to Linked List | LeetCode 114

Medium

Linked List Stack Tree Depth-First Search Binary Tree

Time: O(n)Space: O(1)

Solution Code

Available in:

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public void flatten(TreeNode root) {
        TreeNode current = root;
        while (current != null) {
            if (current.left != null) {
                TreeNode predecessor = current.left;
                while (predecessor.right != null) {
                    predecessor = predecessor.right;
                }

                predecessor.right = current.right;
                current.right = current.left;
                current.left = null;
            }

            current = current.right;
        }
    }
}

View Full Solution on GitHubGitHub Solution View on LeetCodeLeetCode

Problem Info

Description

Problem 114: Flatten Binary Tree to Linked List - Detailed explanation and solution approaches.

Topics

Linked List Stack Tree Depth-First Search Binary Tree

Companies

AndurilAppleGoogleMedia.netMyntraPayPalSalesforceUber

Stats

Difficulty:Medium

Languages:4

Companies:9

Problem #:114

Problem Explanation

💡

Think Before You Code

🤔 Ask Yourself

→What is the input? What output do I need?
→Can I solve a smaller version of this problem first?
→What patterns have I seen in similar problems?

✏️ Try This First

Before looking at the solution, try to solve it on paper with a simple example!

🚀 Try on LeetCode

Solution Approach

📋

Step-by-Step Solution

8 steps

1
Step 1: Initialize a `current` pointer to the root of the tree.
2
Step 2: While `current` is not null, continue the iteration.
3
Step 3: If `current` has a left child:
4
Step 4: Find the rightmost node (`predecessor`) in the left subtree of `current`.
5
Step 5: Set the `right` child of `predecessor` to the `right` child of `current`.
6
Step 6: Set the `right` child of `current` to its `left` child.
7
Step 7: Set the `left` child of `current` to null.
8
Step 8: Move `current` to its `right` child, and repeat from Step 2.

💡

Pro Tip for Students

Try tracing through each step with a small example on paper before coding. Understanding "why" each step happens is more important than memorizing the code!

⚡

Complexity Analysis

⏱️

Time Complexity

O(n)

👍 Linear - Good! Visits each element once.

💾

Space Complexity

O(1)

💪 Constant space - Uses same memory regardless of input!

📝

Why?

The time complexity is O(n) because we traverse each node in the tree at most twice. The nested while loop doesn't mean that we visit the nodes multiple times. The inner loop traverses the left subtree, but each edge traversed is only traversed once across all iterations. The space complexity is O(1) because we are modifying the tree in-place and not using any additional data structures that scale with the input size.

📖New to Big O? Click to learn more

Big O Notation - Quick Guide

O(1)Best - Instant

O(log n)Excellent - Binary Search

O(n)Good - One loop

O(n log n)OK - Sorting

O(n²)Slow - Nested loops

O(2ⁿ)Very Slow - Recursion

Alternative Approaches

Recursive Approach

A recursive approach can also solve this problem using a pre-order traversal. We can recursively flatten the left and right subtrees, and then adjust the pointers of the current node.

Time: O(n)Space: O(n) in the worst case (skewed tree) due to the call stack. O(log n) on balanced tree.

Trade-offs: The recursive approach is often more intuitive to understand but might be less efficient in terms of space complexity due to the call stack, especially for highly unbalanced trees. The iterative approach is generally preferred due to its constant space complexity.

✨

Key Insights

1Insight 1: The key is to perform a pre-order traversal while restructuring the tree. The pre-order traversal order is Node -> Left -> Right.
2Insight 2: We can use an iterative approach with O(1) space complexity, avoiding recursion's call stack overhead.
3Insight 3: For each node, find the rightmost node of its left subtree. Connect this rightmost node to the current node's right subtree. Then move the left subtree to the right, and set the left to null.

📚

Key Terms Explained

For Students

Stack

LIFO structure - Last In, First Out. Like a stack of plates!

Linked List

Elements connected via pointers. Like a chain where each link knows the next.

Tree

Hierarchical structure with nodes. Like a family tree!

Edge Cases

Edge case 1: Empty tree (root is NULL). The algorithm correctly handles this case because the outer `while` loop will not execute.
Edge case 2: A tree with only one node (root has no children). The algorithm correctly handles this case because the `if` condition (`current.left`) will be false, and `current` will immediately become NULL, terminating the process.
Edge case 3: Skewed trees (only left or right children). The algorithm still works correctly because it iterates through the structure and rearranges the pointers as required.

⚠️

Common Mistakes to Avoid

✗Common mistake 1: Incorrectly handling the edge case of an empty tree. Ensuring the code handles NULL root gracefully is essential.

✗Common mistake 2: Failing to set the left child to NULL after moving the left subtree to the right. This is a critical step in creating the linked list structure.

✗Common mistake 3: Not finding the rightmost node of the left subtree correctly. This leads to incorrect restructuring of the tree.

✅

Learning Tip

Every mistake is a learning opportunity! When you make an error, understand why it happened before moving on.

🌍

Where is This Used in Real Life?

💼Real-world scenario 1: Tree serialization and deserialization. Flattening a tree can be a step in serializing a complex tree structure into a linear format for storage or transmission.

🏦Real-world scenario 2: Representing hierarchical data in a flat structure. Sometimes, it's necessary to convert a hierarchical tree structure into a linear linked list representation for processing or display purposes, especially when dealing with limited memory or specific data processing pipelines.

💡Understanding real-world applications helps you see the "why" behind algorithms. It's not just about passing interviews—these concepts power the apps and websites you use every day!

Author's Notes

💡 Key Insight

The dummy node technique prevents edge cases. For cycle detection, Floyd's algorithm is the standard. Always handle empty list and single node cases.

🎯 Interview Tip

Medium problems are the bread and butter of technical interviews. Practice explaining your approach before coding.

⚠️ Watch Out

Losing reference to nodes when modifying pointers. Use temporary variables to save references.

Written by Saswata Mondal

Software Engineer • Algorithms Enthusiast • Interview Coach

👨‍💻

About the Author

👨‍💻

Saswata MondalAuthor400+ LC Problems

B.Tech CSE, IEM Kolkata | LeetCode Rating: 1672 (Top 15%)

Certified: IBM Java Developer, NPTEL Programming in Java

Last updated: September 23, 2024LeetCode Profile GitHub

This solution has been crafted based on my experience solving 400+ LeetCode problems. Each explanation is designed to help you understand the underlying concepts, not just memorize the code.

Community Tips & Insights

In a real interview, always clarify constraints first. Ask about input size and value ranges.

@TechLeadJul 13

Don't forget to handle the edge case when the input is empty. Many candidates miss this in interviews.

@DevExpert92Jul 6

❓

Frequently Asked Questions

Why use a dummy node in linked list problems?

A dummy node simplifies edge cases where the head might change (insertion/deletion at head) or when building a new list. Initialize dummy.next = head, work with dummy.next throughout, and return dummy.next at the end to handle all cases uniformly.

What problems are best solved with a stack?

Stacks excel at: matching problems (parentheses validation), next greater/smaller element, expression evaluation, backtracking, and undo operations. The key pattern is LIFO (Last In, First Out) - when you need to access the most recently added element.

What techniques are commonly tested in medium-difficulty problems?

Medium problems often require combining multiple techniques: two-pointer with hash maps, BFS/DFS with state tracking, dynamic programming with optimization, or divide-and-conquer approaches. They test your ability to recognize patterns and choose the right combination of techniques.

How should I practice algorithm problems effectively?

Focus on understanding patterns rather than memorizing solutions. After solving a problem, review optimal solutions and understand the intuition. Group similar problems to recognize patterns. Practice explaining your approach out loud. Review problems after a few days to test retention.

What is the optimal approach for "Flatten Binary Tree to Linked List"?

For this medium-level Linked List problem, the key is to identify the core pattern. Analyze the input constraints to determine acceptable time complexity. Consider whether stack techniques can optimize the solution. Always handle edge cases and validate your approach with examples before coding.

🤖 Need help with this problem?