Flatten the Tree Into a Right-Leaning Chain

Medium25–30 min

Topics

Binary TreeDFSTree TransformationIn-Place

Companies

AmazonMicrosoftFacebookAdobeBloomberg

You are given the root of a binary tree. Rearrange it in place — reusing the same nodes — into a "chain" that leans to the right: every node has no left child, and its right child is the node that comes next in the pre-order traversal of the original tree (node, then its left subtree, then its right subtree). Return the root of the rearranged tree.

You could record the pre-order in a list and then relink the nodes, but the rearrangement can also be done with a single pointer walking down the chain, splicing each right subtree behind the last node of the left subtree.

Test Case 1:

Input:root = [12, 6, 15, 3, 9, null, 18]

Output:[12, null, 6, null, 3, null, 9, null, 15, null, 18]

Explanation:The original pre-order is 12, 6, 3, 9, 15, 18. After flattening every node has only a right child, forming the chain 12 → 6 → 3 → 9 → 15 → 18.

Test Case 2:

Input:root = [4, 2]

Output:[4, null, 2]

Explanation:The lone left child moves to the right side.

Test Case 3:

Input:root = []

Output:[]

Explanation:Nothing to flatten.

Constraints

◆0 ≤ number of nodes ≤ 100
◆−100 ≤ node.val ≤ 100
◆The tree is given as its root node (null for an empty tree); each node has a val, a left child and a right child
◆Rearrange the tree IN PLACE (reuse the same nodes) so that every node has no left child and its right child is the next node in the pre-order of the original tree (node, then its left subtree, then its right subtree). Return the root. The result is checked as a level-order list

🚀

Try the Dry Run

Don't just read the solution — watch it execute, one step at a time.

Approach & Solutions

Brute Force — Collect the Pre-Order, Then Re-Link the Nodes

Good

First record every node in pre-order (node, then left subtree, then right subtree) in a list — nothing is changed yet, so the traversal is not disturbed by relinking. Then go through the list and rewire each node: its left child becomes null and its right child becomes the next node in the list (the last node's right child is null). It is easy to get right, but the list of all n nodes costs O(n) extra space; time is O(n).

TimeO(n)

SpaceO(n)

Java

Try it out

class Solution {
    public TreeNode flattenInPreorder(TreeNode root) {
        List<TreeNode> order = new ArrayList<>();
        collect(root, order);
        for (int i = 0; i < order.size(); i++) {
            order.get(i).left = null;
            order.get(i).right = i + 1 < order.size() ? order.get(i + 1) : null;
        }
        return root;
    }

    private void collect(TreeNode node, List<TreeNode> order) {
        if (node == null) return;
        order.add(node);
        collect(node.left, order);
        collect(node.right, order);
    }
}

Optimal — Splice the Right Subtree Onto the Left Subtree's Last Node

Optimal

Walk down the chain being built with a pointer cur. If cur has a left subtree, find the LAST node of that subtree in pre-order — the rightmost node, reached by going right until you cannot — and hang cur's current right subtree from it: in pre-order that whole right subtree comes right after the left subtree. Then move the left subtree into the right slot and set left to null. Step to cur's right child and repeat. Every node is spliced at most once and each rightmost search only walks parts of the tree that are never searched again, so it is O(n) time and needs no list and no recursion: O(1) extra space.