Talentd
For employersSign in
JobsInternshipsPracticeResume toolsCompaniesArticles
For employers
FleetCode
Make and follow sheets.Sign in

Flatten Binary Tree to Linked List solution and explanation

MediumBinary TreeDepth-First SearchLinked ListStack6 min read71.6% acceptanceUpdated 9 Apr 2026
Asked atJosh TechnologyMicrosoftAndurilGoogleAmazonMeta
+2 moreBloombergOracle
Practise Flatten Binary Tree to Linked List
14:27
Flatten Binary Tree to Linked List - Leetcode 114 - PythonNeetCode · 14:27 · 70K viewsWatch on YouTube
9 more videos on this problem
  1. Flatten Binary Tree to Linked List - Leetcode 114 - PythonNeetCode · 14:27 · 70K views
  2. LeetCode Flatten Binary Tree to Linked List Explained - JavaNick White · 5:23 · 40K views
  3. Flatten Binary Tree to Linked List | DSA Series : L.95Shradha Khapra · 15:43 · 38K views
  4. Flatten Binary Tree to Linked List | Live Coding with Explanation | Leetcode - 114Algorithms Made Easy · 12:28 · 17K views
  5. Flatten Binary Tree to Linked List | Leetcode #114Techdose · 15:43 · 9K views
  6. Flatten Binary Tree to Linked List | LeetCode 114Java2Novice · 16:52 · 5K views
  7. LEETCODE SOLUTION #114 -- FLATTEN BINARY TREE TO LINKED LIST IN PLACE (WITH CODE)Alex Solves Algorithms · 25:05 · 4K views
  8. Leetcode - Flatten Binary Tree to Linked List (Python)Timothy H Chang · 5:20 · 3K views
  9. Flatten Binary Tree to Linked List | LeetCode 114 | Coders CampCoders Camp · 7:59 · 679 views
  10. L38. Flatten a Binary Tree to Linked List | 3 Approaches | C++ | Javatake U forward · 21:51 · 328K views

The problem

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)?

Approach overview

Problem Overview: You receive the root of a binary tree and must transform it into a linked list in-place. The linked list should follow the same order as a preorder traversal (root → left → right). Every node’s left pointer becomes null, and the right pointer acts as the next pointer in the list.

Approach 1: Recursive Pre-order Traversal (O(n) time, O(h) space)

This approach uses a classic Depth-First Search recursion that processes nodes in preorder. Maintain a reference to the previously visited node. During traversal, set prev.right = current and prev.left = null to build the linked structure incrementally. The key insight is to traverse the right subtree after the left while rewiring pointers as you go. Time complexity is O(n) because each node is visited once. Space complexity is O(h), where h is the tree height due to the recursion stack.

Approach 2: Iterative Pre-order Traversal with Stack (O(n) time, O(n) space)

This method simulates preorder traversal using an explicit stack. Push the root node first. For each popped node, push its right child and then its left child so the left subtree is processed next. Rewire pointers by setting the current node’s right pointer to the next node on the stack and clearing left. The stack preserves preorder ordering without recursion. Time complexity remains O(n) since each node is pushed and popped once. Space complexity becomes O(n) in the worst case for skewed trees.

Both methods restructure the Binary Tree in-place without creating new nodes. The recursive approach is compact and mirrors the definition of preorder traversal. The iterative stack approach avoids recursion depth limits and provides more explicit control over traversal order.

Recommended for interviews: The recursive preorder DFS is usually the expected explanation because it clearly demonstrates pointer manipulation during traversal. Interviewers want to see that you understand preorder processing and in-place tree modification. The iterative stack version is a strong alternative when discussing recursion limits or implementing traversal without the call stack.

Approach 1: Recursive Pre-order Traversal

This approach involves a recursive pre-order traversal of the tree. The idea is to recursively flatten the left and right subtrees, then append the flattened left subtree between the root and the flattened right subtree.

The steps are as follows:

  1. Recursively flatten the left and right subtrees.
  2. Save the right subtree, then set the root's right to the left subtree and left to null.
  3. Traverse to the end of the new right subtree (originally left subtree) and append the saved right subtree.

This leverage the pre-order traversal principle: Root → Left → Right.

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

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

        left = root.left
        right = root.right

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

        root.right = left
        curr = root
        while curr.right:
            curr = curr.right
        curr.right = right
class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { val = x; }
}

public 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 curr = root;
        while (curr.right != null) {
            curr = curr.right;
        }
        curr.right = right;
    }
}
#include <iostream>
using namespace std;

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

void flatten(TreeNode* root) {
    if (!root) return;
    TreeNode* left = root->left;
    TreeNode* right = root->right;

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

    root->right = left;
    TreeNode* current = root;
    while (current->right) {
        current = current->right;
    }
    current->right = right;
}
function TreeNode(val, left, right) {
    this.val = (val===undefined ? 0 : val)
    this.left = (left===undefined ? null : left)
    this.right = (right===undefined ? null : right)
}

var flatten = function(root) {
    if (!root) return;

    let left = root.left;
    let right = root.right;

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

    root.right = left;
    let current = root;
    while (current.right !== null) {
        current = current.right;
    }
    current.right = right;
};
#include <stdio.h>

struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
};

void flatten(struct TreeNode* root) {
    if (!root) return;
    struct TreeNode* left = root->left;
    struct TreeNode* right = root->right;

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

    root->right = left;
    struct TreeNode* current = root;
    while (current->right) {
        current = current->right;
    }
    current->right = right;
}
public class TreeNode {
    public int val;
    public TreeNode left;
    public TreeNode right;
    public TreeNode(int val=0, TreeNode left=null, TreeNode right=null) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

public 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 curr = root;
        while (curr.right != null) {
            curr = curr.right;
        }
        curr.right = right;
    }
}

In Python, this solution follows the recursive approach to rearrange the given binary tree. The 'left' and 'right' are stored initially to rearrange nodes correctly after flattening both subtrees.

Complexity

Time Complexity: O(n) since each node is visited once.
Space Complexity: O(n) due to recursion stack space in worst-case scenario.

Try this approach in the editor

Approach 2: Iterative Pre-order Traversal

This approach simplifies the recursive method by using a stack to maintain state information. By using controlled use of stack structures, we can modify the tree iteratively.

The algorithm progresses with these steps:

  1. Construct a stack and push the root.
  2. Process nodes using a stack to handle traversal iteratively, similar to pre-order.
  3. While processing each node, capture its left and right children, alter pointers, and advance the iteration.

This achieves similar logic as recursion but without directly using the call stack by using our custom stack for maintaining traversal state.

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

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

        stack = [root]

        while stack:
            current = stack.pop()

            if current.right:
                stack.append(current.right)

            if current.left:
                stack.append(current.left)

            if stack:
                current.right = stack[-1]

            current.left = None
import java.util.Stack;

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { val = x; }
}

public class Solution {
    public void flatten(TreeNode root) {
        if (root == null) return;
        Stack<TreeNode> stack = new Stack<>();
        stack.push(root);

        while (!stack.isEmpty()) {
            TreeNode current = stack.pop();

            if (current.right != null) {
                stack.push(current.right);
            }
            if (current.left != null) {
                stack.push(current.left);
            }

            if (!stack.isEmpty()) {
                current.right = stack.peek();
            }
            current.left = null;
        }
    }
}
#include <iostream>
#include <stack>
using namespace std;

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

void flatten(TreeNode* root) {
    if (!root) return;
    stack<TreeNode*> stk;
    stk.push(root);

    while (!stk.empty()) {
        TreeNode* current = stk.top();
        stk.pop();

        if (current->right) {
            stk.push(current->right);
        }
        if (current->left) {
            stk.push(current->left);
        }

        if (!stk.empty()) {
            current->right = stk.top();
        }
        current->left = NULL;
    }
}
function TreeNode(val, left, right) {
    this.val = (val===undefined ? 0 : val)
    this.left = (left===undefined ? null : left)
    this.right = (right===undefined ? null : right)
}

var flatten = function(root) {
    if (!root) return;
    let stack = [root];

    while (stack.length > 0) {
        let current = stack.pop();

        if (current.right !== null) {
            stack.push(current.right);
        }
        if (current.left !== null) {
            stack.push(current.left);
        }

        if (stack.length > 0) {
            current.right = stack[stack.length - 1];
        }
        current.left = null;
    }
};
#include <stdio.h>
#include <stdlib.h>

struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
};

struct StackNode {
    struct TreeNode* node;
    struct StackNode* next;
};

void push(struct StackNode** stack, struct TreeNode* node) {
    struct StackNode* new_node = (struct StackNode*)malloc(sizeof(struct StackNode));
    new_node->node = node;
    new_node->next = *stack;
    *stack = new_node;
}

struct TreeNode* pop(struct StackNode** stack) {
    if (!*stack) return NULL;
    struct StackNode* tmp = *stack;
    struct TreeNode* node = tmp->node;
    *stack = tmp->next;
    free(tmp);
    return node;
}

void flatten(struct TreeNode* root) {
    if (!root) return;
    struct StackNode* stack = NULL;
    push(&stack, root);

    while (stack) {
        struct TreeNode* curr = pop(&stack);

        if (curr->right) {
            push(&stack, curr->right);
        }
        if (curr->left) {
            push(&stack, curr->left);
        }

        if (stack) {
            curr->right = stack->node;
        }
        curr->left = NULL;
    }
}
using System.Collections.Generic;

public class TreeNode {
    public int val;
    public TreeNode left;
    public TreeNode right;
    public TreeNode(int val=0, TreeNode left=null, TreeNode right=null) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

public class Solution {
    public void Flatten(TreeNode root) {
        if (root == null) return;
        Stack<TreeNode> stack = new Stack<TreeNode>();
        stack.Push(root);

        while (stack.Count > 0) {
            TreeNode current = stack.Pop();

            if (current.right != null) {
                stack.Push(current.right);
            }
            if (current.left != null) {
                stack.Push(current.left);
            }

            if (stack.Count > 0) {
                current.right = stack.Peek();
            }
            current.left = null;
        }
    }
}

The Python iteration utilizes a stack to simulate recursion for flattening the tree by pre-order alignment. It extracts nodes from the stack in `right-first` fashion during each traversal iteration.

Complexity

Time Complexity: O(n), since each node is assessed once.
Space Complexity: O(n) corresponding to stack size requirements for deepest branches or nodes.

Try this approach in the editor

Approach 3: Find Predecessor Node

The visit order of preorder traversal is "root, left subtree, right subtree". After the last node of the left subtree is visited, the right subtree node of the root node will be visited next.

Therefore, for the current node, if its left child node is not null, we find the rightmost node of the left subtree as the predecessor node, and then assign the right child node of the current node to the right child node of the predecessor node. Then assign the left child node of the current node to the right child node of the current node, and set the left child node of the current node to null. Then take the right child node of the current node as the next node and continue processing until all nodes are processed.

The time complexity is O(n), where n is the number of nodes in the tree. The space complexity is O(1).

/**
 * Definition for a binary tree node.
 * class TreeNode {
 *     val: number
 *     left: TreeNode | null
 *     right: TreeNode | null
 *     constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.left = (left===undefined ? null : left)
 *         this.right = (right===undefined ? null : right)
 *     }
 * }
 */

/**
 Do not return anything, modify root in-place instead.
 */
function flatten(root: TreeNode | null): void {
    while (root !== null) {
        if (root.left !== null) {
            let pre = root.left;
            while (pre.right !== null) {
                pre = pre.right;
            }
            pre.right = root.right;
            root.right = root.left;
            root.left = null;
        }
        root = root.right;
    }
}
/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func flatten(root *TreeNode) {
	for root != nil {
		if root.Left != nil {
			pre := root.Left
			for pre.Right != nil {
				pre = pre.Right
			}
			pre.Right = root.Right
			root.Right = root.Left
			root.Left = nil
		}
		root = root.Right
	}
}
// Definition for a binary tree node.
// #[derive(Debug, PartialEq, Eq)]
// pub struct TreeNode {
//   pub val: i32,
//   pub left: Option<Rc<RefCell<TreeNode>>>,
//   pub right: Option<Rc<RefCell<TreeNode>>>,
// }
//
// impl TreeNode {
//   #[inline]
//   pub fn new(val: i32) -> Self {
//     TreeNode {
//       val,
//       left: None,
//       right: None
//     }
//   }
// }
use std::cell::RefCell;
use std::rc::Rc;
impl Solution {
    #[allow(dead_code)]
    pub fn flatten(root: &mut Option<Rc<RefCell<TreeNode>>>) {
        if root.is_none() {
            return;
        }
        let mut v: Vec<Option<Rc<RefCell<TreeNode>>>> = Vec::new();
        // Initialize the vector
        Self::pre_order_traverse(&mut v, root);
        // Traverse the vector
        let n = v.len();
        for i in 0..n - 1 {
            v[i].as_ref().unwrap().borrow_mut().left = None;
            v[i].as_ref().unwrap().borrow_mut().right = v[i + 1].clone();
        }
    }

    #[allow(dead_code)]
    fn pre_order_traverse(
        v: &mut Vec<Option<Rc<RefCell<TreeNode>>>>,
        root: &Option<Rc<RefCell<TreeNode>>>,
    ) {
        if root.is_none() {
            return;
        }
        v.push(root.clone());
        let left = root.as_ref().unwrap().borrow().left.clone();
        let right = root.as_ref().unwrap().borrow().right.clone();
        Self::pre_order_traverse(v, &left);
        Self::pre_order_traverse(v, &right);
    }
}
Try this approach in the editor

Approach 4: Default Approach

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func flatten(root *TreeNode) {
	for root != nil {
		left, right := root.Left, root.Right
		root.Left = nil
		if left != nil {
			root.Right = left
			for left.Right != nil {
				left = left.Right
			}
			left.Right = right
		}
		root = root.Right
	}
}
Try this approach in the editor

Complexity comparison

ApproachComplexity
Recursive Pre-order Traversal

Time Complexity: O(n) since each node is visited once.
Space Complexity: O(n) due to recursion stack space in worst-case scenario.

Iterative Pre-order Traversal

Time Complexity: O(n), since each node is assessed once.
Space Complexity: O(n) corresponding to stack size requirements for deepest branches or nodes.

Find Predecessor Node–
Default Approach–

Complexity analysis

ApproachTimeSpaceWhen to Use
Recursive Pre-order TraversalO(n)O(h)Preferred in interviews; concise DFS logic and natural preorder traversal
Iterative Pre-order Traversal (Stack)O(n)O(n)When avoiding recursion or handling deep trees where recursion depth could overflow

Frequently asked questions

Is Flatten Binary Tree to Linked List easy or hard?

Flatten Binary Tree to Linked List is generally classified as a medium difficulty problem. The traversal itself is straightforward, but correctly modifying pointers in-place while preserving preorder order requires careful reasoning about tree structure.

Flatten Binary Tree to Linked List Python/Java solution

Python and Java solutions typically implement preorder DFS. The recursive version keeps a global or class-level previous node reference and updates pointers while traversing. An alternative iterative solution uses a stack to simulate preorder traversal while rewiring nodes in-place.

How to solve Flatten Binary Tree to Linked List in O(n)?

Perform a preorder traversal of the tree and rewire pointers during the visit. For each node, set the previous node’s right pointer to the current node and clear the left pointer. Continue processing left then right children. This ensures each node is processed once, giving O(n) time complexity.

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

The most common approach uses preorder depth-first traversal and rewires pointers while visiting nodes. A recursive DFS keeps track of the previously visited node and connects it to the current node using the right pointer. This runs in O(n) time and O(h) space where h is the tree height. Many interviewers expect this preorder-based solution.

Is Flatten Binary Tree to Linked List asked at Google/Amazon/Meta?

Flatten Binary Tree to Linked List is a common medium-level binary tree problem frequently reported in interviews at companies like Amazon, Google, Meta, and Microsoft. It tests depth-first traversal, pointer manipulation, and understanding of tree structure transformations.

What data structure is used in Flatten Binary Tree to Linked List?

The problem primarily uses binary trees combined with depth-first search traversal. Implementations often rely on recursion or an explicit stack to maintain preorder traversal order. The final structure behaves like a singly linked list using the right pointer.

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

The time complexity is O(n) because every node in the binary tree is visited exactly once during traversal. Pointer updates are constant-time operations for each node. Space complexity is O(h) with recursion or O(n) when using an explicit stack in the iterative approach.

Comments

Next problem · similarFlatten a Multilevel Doubly Linked ListMedium
Now write it yourselfClose this page and solve Flatten Binary Tree to Linked List in the editor, without looking.
Practise Flatten Binary Tree to Linked List