Flatten Binary Tree to Linked List

Medium
1911.

Flatten Binary Tree to Linked List

Flatten Binary Tree to Linked List is a medium coding problem on depth-first search, trees and stack, asked in Amazon, Microsoft and Meta interviews.

Given the root of a binary tree, flatten it in place into a "linked list" made of the same nodes:

  • the list follows the tree's preorder (node, left subtree, right subtree);
  • each node's right pointer points to the next node of the list, and its left pointer is null.

Return the root once the tree is flattened.

Example 1

Input
root = [1,2,5,3,4,null,6]
Output
[1,null,2,null,3,null,4,null,5,null,6]
Explanation
The preorder is 1, 2, 3, 4, 5, 6; each node becomes the right child of the one before it.

Example 2

Input
root = []
Output
[]
Explanation
An empty tree stays empty.

Example 3

Input
root = [0]
Output
[0]
Explanation
A single node is already a list.

Constraints

  • 0 <= number of nodes <= 2000
  • -100 <= Node.val <= 100

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

Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * Definition for a binary tree node (provided by the judge — do not redefine it):
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {TreeNode}
 */
var flatten = function(root) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Flatten Binary Tree to Linked List — Problem & Solution

Flatten Binary Tree to Linked List solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.

Flatten Binary Tree to Linked List is a medium coding problem on depth-first search, trees and stack, asked in Amazon, Microsoft and Meta interviews.

Problem statement

Given the root of a binary tree, flatten it in place into a "linked list" made of the same nodes:

  • the list follows the tree's preorder (node, left subtree, right subtree);
  • each node's right pointer points to the next node of the list, and its left pointer is null.

Return the root once the tree is flattened.

Example 1

Input: root = [1,2,5,3,4,null,6]
Output: [1,null,2,null,3,null,4,null,5,null,6]
Explanation: The preorder is 1, 2, 3, 4, 5, 6; each node becomes the right child of the one before it.

Example 2

Input: root = []
Output: []
Explanation: An empty tree stays empty.

Example 3

Input: root = [0]
Output: [0]
Explanation: A single node is already a list.

Constraints

  • 0 <= number of nodes <= 2000
  • -100 <= Node.val <= 100

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

Hints for Flatten Binary Tree to Linked List

  1. Hint 1

    In preorder, a node's whole left subtree comes right after it, and its right subtree comes after the last node of the left subtree.

  2. Hint 2

    The last node of a left subtree in preorder is its rightmost node — follow right pointers from the left child until there are none.

  3. Hint 3

    At each node with a left child: hang the node's right subtree off that rightmost node, move the left subtree to the right, clear the left pointer, then continue to the right.

How to solve Flatten Binary Tree to Linked List

Splice each left subtree in between a node and its right subtree. The left subtree's last preorder node — its rightmost node — is where the old right subtree reattaches. Doing this top-down along the right spine flattens the tree with no stack.

Approach

  1. Let cur be the root.
  2. While cur is not null: if it has a left child, find pre, the rightmost node of the left subtree.
  3. Set pre.right = cur.right, then cur.right = cur.left and cur.left = null.
  4. Move cur to cur.right and repeat.
  5. Return the root.

Why it works

After the splice, the order that follows cur is: its old left subtree (in which pre is the last node in preorder) and then its old right subtree — exactly the preorder of cur's subtree. The splice keeps every subtree's internal preorder, and the walk then repeats the step on every node of the new right chain, so when it ends no left pointer remains and the chain is the full preorder.

Complexity

  • Time — O(n): each node is passed over a constant number of times as cur and as part of a rightmost search
  • Space — O(1)

Pitfalls

  • Save the right subtree before overwriting cur.right, or it is lost.
  • Clear left on every node — a list node with a leftover left child is not flattened.

Reference solution

Python

from typing import Optional

def flatten(root: Optional[TreeNode]) -> Optional[TreeNode]:
    cur = root
    while cur:
        if cur.left:
            pre = cur.left
            while pre.right:
                pre = pre.right
            pre.right = cur.right
            cur.right = cur.left
            cur.left = None
        cur = cur.right
    return root

Java

public static TreeNode flatten(TreeNode root) {
    TreeNode cur = root;
    while (cur != null) {
        if (cur.left != null) {
            TreeNode pre = cur.left;
            while (pre.right != null) pre = pre.right;
            pre.right = cur.right;
            cur.right = cur.left;
            cur.left = null;
        }
        cur = cur.right;
    }
    return root;
}

C++

TreeNode* flatten(TreeNode* root) {
    TreeNode* cur = root;
    while (cur) {
        if (cur->left) {
            TreeNode* pre = cur->left;
            while (pre->right) pre = pre->right;
            pre->right = cur->right;
            cur->right = cur->left;
            cur->left = nullptr;
        }
        cur = cur->right;
    }
    return root;
}

JavaScript

var flatten = function(root) {
    var cur = root;
    while (cur !== null) {
        if (cur.left !== null) {
            var pre = cur.left;
            while (pre.right !== null) pre = pre.right;
            pre.right = cur.right;
            cur.right = cur.left;
            cur.left = null;
        }
        cur = cur.right;
    }
    return root;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 201 depth-first search problems · the whole catalogue

Learn the technique: Depth-First Search (DFS) · Binary Trees and Tree Traversals