Skip to content

Learn

Theory

CS Fundamentals

You

Today's problem

Home
Problems
Flatten Binary Tree to Linked List

Related problems

Validate Binary Search Tree
Same Tree
Symmetric Tree
Binary Tree Maximum Path Sum
Binary Tree Right Side View
Kth Smallest Element in a BST
Serialize and Deserialize Binary Tree
Flatten Nested List Iterator
Convert Sorted Array to Binary Search Tree
Pascal's Triangle

Flatten Binary Tree to Linked List

medium

Flatten Binary Tree to Linked List

Linked List
Stack
Tree
DFS
Binary Tree

You get the root of a binary tree. Flatten it into a chain, reusing the same nodes:

the chain visits the nodes in preorder: a node first, then everything in its left subtree, then everything in its right subtree;
each node's right pointer leads to the next node of the chain, and the last node's right is null;
every left pointer is null.

Change the tree in place and return nothing: the answer is the tree read from root once your function finishes. It is printed like any tree, level by level with null for a missing child, so a flat chain prints as [a,null,b,null,c,…].

Examples

Example 1

Input

root

Output

Explain:

The whole left subtree of 5 (3, 2, 4) comes straight after it, ahead of its right subtree (8, 9).

Example 2

Input

root

Output

Explain:

6 was the left child of 1, so it moves to be its right child.

Example 3

Input

root

(empty tree)

Output

(empty tree)

Explain:

An empty tree stays empty.

Constraints

The tree has between 0 and 2000 nodes.
-100 <= Node.val <= 100

Stuck? Hint 1

In preorder, a node's whole left subtree comes straight after it, and its right subtree comes after the last node of that left subtree. So the right subtree belongs hanging off the rightmost node of the left subtree.

Input

Expected Output

Ctrl / ⌘ + Enter