LESSON 312 OF 348 · BINARY TREES

Flatten Binary Tree in TypeScript: In-Place Reverse Postorder

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]

STEP 1 OF 9

Guided

Ctrl + Enter to check

Flatten Binary Tree in TypeScript, explained

Problem overview

The method flatten receives the root of a binary tree and rewires it in place into a "linked list" built from the same nodes. Every node's right pointer must point to the next node, every left pointer must be null, and the nodes must appear in preorder: a node, then its left subtree, then its right subtree. The method returns nothing; the caller keeps using the same root.

In the first example the tree is [1,2,5,3,4,null,6]: node 1 has children 2 and 5, node 2 has children 3 and 4, and node 5 has a right child 6. Its preorder is 1, 2, 3, 4, 5, 6, so after flattening, 1 points right to 2, 2 to 3, and so on up to 6. An empty tree stays empty, and a single node stays a single node.

Approach: build the list from the back

A natural idea is to collect the nodes in preorder and then link them. That works but needs an extra array of n nodes. The lesson avoids it by building the list backwards.

Visit the tree in the mirrored order of postorder: right subtree, then left subtree, then the node. That is exactly the preorder sequence reversed. Keep a pointer, lastNode, to the head of the list built so far. When the visit reaches a node, everything that comes after it in preorder is already linked, and lastNode is the first of those nodes. So the node only has to point right at lastNode, clear left, and become the new lastNode.

Take a node 1 with left child 2 and right child 3. The visit goes 3, 2, 1. Node 3 points to null (nothing is after it) and becomes the head. Node 2 points to 3 and becomes the head. Node 1 points to 2. The list is 1, 2, 3, which is the preorder of that tree.

Step by step

Reset this.lastNode to null at the start of flatten. It stands for the head of the list built so far, which is empty. Storing it on this lets every recursive call share it. TypeScript wants each property declared, so the class gets the line lastNode: any;.
Call this.dfs(root) to flatten the whole tree.
Declare dfs above flatten with one parameter, root. It rewires nodes and returns nothing.
Base case. A null node has nothing to flatten, so return.
Recurse on the right subtree first. Its nodes are the last ones in preorder, so they must be linked before anything that points at them.
Recurse on the left subtree. When this returns, lastNode is the first node of the left subtree, which is exactly the node that follows root in preorder.
Point root.right at this.lastNode. That links the node to what follows it. If the left subtree was empty, lastNode is the head of the right part, which is also correct.
Set root.left to null. The left subtree is now reachable through the right chain, so nothing is lost.
Record root in this.lastNode. It is the head of the part of the list built so far.

The solution in TypeScript

class Solution {
    lastNode: any;
    dfs(root) {
        if (!root) {
            return;
        }
        this.dfs(root.right);
        this.dfs(root.left);
        root.right = this.lastNode;
        root.left = null;
        this.lastNode = root;
    }

    flatten(root) {
        this.lastNode = null;
        this.dfs(root);
    }
}

TypeScript details worth knowing:

Properties must be declared. Assigning this.lastNode without the lastNode: any; line makes the compiler report that the property doesn't exist on Solution. any is used because the parameters root are untyped here, so a precise node type isn't available.
Untyped parameters are any. With the compiler settings of these lessons, root without an annotation is allowed and has type any, so root.right is accepted. Types are erased when the code compiles to JavaScript anyway, so the program behaves the same with or without them.
State on this. The helper reads and writes one shared value across all recursive calls. Because flatten resets it to null first, calling flatten again on the same Solution object starts clean.
Order of the assignments. root.right = this.lastNode must come before this.lastNode = root. Swapped, the node would point to itself.

Complexity

Time: O(n). Each node is visited once, and each visit does a few pointer assignments.

Space: O(h), where h is the height of the tree, for the recursion. No array of nodes is created. A tree shaped like a long chain has h = n, and a very deep one can overflow the call stack.

Edge cases and common mistakes

An empty tree. root is null, dfs returns at once and nothing changes.
A single node. root.right becomes null (the value of lastNode), root.left is already null, and the node is unchanged.
Doing left first. If dfs(root.left) ran before dfs(root.right), the nodes would be linked in an order that is no longer preorder, because lastNode would hold the wrong head when root is linked.
Forgetting root.left = null. The list would still be reachable through right pointers, but leftover left pointers would break the requirement and any check that follows both pointers.
Not resetting lastNode. On a second call, the last node of the new list would point at the head of the previous result.
Returning something. The task changes the tree in place. The caller reads the result by following right from the original root.

Testing

[1,2,5,3,4,null,6] becomes the chain 1, 2, 3, 4, 5, 6.
An empty tree stays empty.
[0] stays [0].
Node 1 with left child 2 and right child 3 becomes 1, 2, 3, with every left equal to null.

Keep going with TypeScriptAbout 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.

Start learning free