LESSON 312 OF 348 · BINARY TREES

Flatten Binary Tree in Kotlin: Reverse Preorder with a Property

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 10

Guided

Ctrl + Enter to check

KOTLIN · BINARY TREES

Flatten Binary Tree in Kotlin, explained

Problem overview

The function flatten receives the root of a binary tree, a TreeNode?, and returns nothing. It must rewire the tree in place so that it becomes a "linked list" made of the same TreeNode objects: every left pointer is null, every right pointer points to the next node, and the nodes appear in preorder (node, then left subtree, then right subtree).

For the tree with root 1, children 2 and 5, node 2 having children 3 and 4, and node 5 having the right child 6, preorder is 1, 2, 3, 4, 5, 6. After flattening, node 1's right pointer leads to 2, then 3, 4, 5 and 6, and no node has a left child. An empty tree stays empty, and a single node stays as it is.

Approach: build the list from the back

The obvious plan is to flatten the left subtree, flatten the right subtree, and then splice the right list onto the end of the left one. That needs a walk to find the end of the left list.

A simpler plan processes the nodes in reverse preorder: right subtree first, then left subtree, then the node. Preorder is node, left, right, so the reverse is right, left, node. When a node is finally handled, everything that follows it in the final list has already been flattened. A variable lastNode holds the head of that finished part. The node only has to point its right at lastNode, clear its left, and become the new lastNode.

Trace it on a root 1 with left child 2 and right child 3. The recursion handles 3 first: its right becomes null (nothing was flattened yet) and lastNode is 3. Then 2: its right becomes 3, and lastNode is 2. Last, 1: its right becomes 2 and its left is cleared. The list is 1, 2, 3.

Step by step

Declare a property lastNode of type TreeNode?, starting at null. It lives on the Solution object, so every recursive call reads and updates the same one.
Reset it in flatten. A Solution object may be used for several trees, and the property keeps its value between calls. Without the reset, the last node of a new list would point into the previous tree.
Call dfs(root) to flatten the entire tree.
Declare dfs with a TreeNode? parameter. It returns nothing, because it rewires nodes in place.
Return on a null root. An empty subtree contributes nothing.
Recurse on root.right first. The whole right side is flattened and recorded in lastNode before this node is touched.
Recurse on root.left next. The last node of the left list links to the head of the right list, and the head of the left list is what ends up directly after root.
Set root.right = lastNode, linking this node to the list built so far.
Set root.left = null. The left subtree is already part of the list through right pointers, so nothing is lost.
Set lastNode = root. This node is now the head of the flattened part, and the node handled next links to it.

The solution in Kotlin

class Solution {
    fun dfs(root: TreeNode?) {
        if (root == null) {
            return
        }
        dfs(root.right)
        dfs(root.left)
        root.right = lastNode
        root.left = null
        lastNode = root
    }

    var lastNode: TreeNode? = null
    fun flatten(root: TreeNode?) {
        lastNode = null
        dfs(root)
    }
}

The Kotlin details worth a closer look:

A property declared after its use. dfs uses lastNode even though the property is declared below it. Inside a class, members can refer to each other in any order.
Properties keep their value. var lastNode: TreeNode? = null is initialised once, when the Solution object is created. That is why flatten sets it to null itself.
The type must be nullable. The first node to be linked points to nothing, so lastNode needs TreeNode?. This also matches root.right, which is a TreeNode?.
Smart cast. After the root == null check, root is treated as a non-null TreeNode, so root.right and root.left need no ?.. Assigning to them is allowed because the lesson's TreeNode declares them as var.
Order of the two recursive calls. Both subtrees are processed before the node's pointers change, so dfs(root.left) still sees the original left subtree.

Complexity

Time: O(n) for n nodes. Each node is processed once, with a constant number of assignments.

Space: O(h) for the recursion, where h is the height of the tree. A balanced tree has h near log n, while a tree shaped like a chain has h = n. No new nodes are created, so the extra memory is only the call stack and one reference.

Edge cases and common mistakes

Empty tree. flatten(null) resets lastNode, returns at once and changes nothing.
Single node. A root of 0 gets right = null and left = null, so it is unchanged.
Forgetting to clear left. The list would still contain the old left pointers, and the tree would not be flat.
Skipping the reset of lastNode. Reusing a Solution for a second tree would link that tree's final node to the previous list.
Recursing left first. With this "build from the back" technique the left list would be linked first and end up after the right one, breaking preorder.
Returning something. The task changes the tree in place, and flatten returns nothing.

Testing

The tree 1 (left 2 with children 3 and 4, right 5 with right child 6) flattens to the chain 1, 2, 3, 4, 5, 6.
Root 1 with children 2 and 3 flattens to 1, 2, 3.
A single node 0 stays 0.
null stays null.

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

Start learning free