Start learning free

LESSON 352 OF 442 · BINARY TREES

Recover a Tree From Preorder Traversal in Kotlin: O(n) with a Stack

Practice O(n) Read the full explanation

We walk a binary tree in preorder: first a node, then its whole left subtree, then its whole right subtree. For every node we write D dashes, where D is the node's depth, followed right away by the node's value. The root has depth 0, so it has no dashes; its children have depth 1, their children depth 2, and so on.

If a node has only one child, that child is its left child.

Given the string traversal written this way, rebuild the tree and return its root.

The tests print the tree you return level by level, from left to right, with null where a child is missing and the trailing nulls left out. For example, [1,2,null,3] is the tree with root 1, 2 as its left child and 3 as the left child of 2.

Example 1:

Input: traversal = "1-2--3--4-5--6--7"
Output: [1,2,5,3,4,6,7]
       1
     /   \
    2     5
   / \   / \
  3   4 6   7

Explanation: "-2" and "-5" have one dash: they are the root's children, 2 first, so 2 is the left one. "--3" and "--4" come right after "-2", so they are the children of 2; "--6" and "--7" come after "-5", so they are the children of 5.

Example 2:

Input: traversal = "1-2--3---4-5--6---7"
Output: [1,2,5,3,null,6,null,4,null,7]
        1
       / \
      2   5
     /   /
    3   6
   /   /
  4   7

Explanation: After "---4" (depth 3) comes "-5" (depth 1): the depth goes back up by two levels at once, so 5 is the second child of the root, its right child. Every node with a single child has it on the left.

Example 3:

Input: traversal = "5-12--7---40--9"
Output: [5,12,null,7,9,40]
      5
     /
    12
   /  \
  7    9
 /
40

Explanation: Values can have several digits: the dashes before a node end where its digits start. The root 5 has a single child, 12, so it is a left child.

Constraints:

The number of nodes in the tree is in the range [1, 1000].
Every node's value is between 1 and 10⁹.
traversal is a valid preorder walk of a tree, written as described above.

STEP 1 OF 18

Guided

Ctrl + Enter to check

KOTLIN · BINARY TREES

Recover Tree From Preorder in Kotlin, explained

Problem overview

A binary tree is written as a string by walking it in preorder: a node, then its whole left subtree, then its whole right subtree. Before each node's value come as many dashes as the node's depth, with the root at depth 0. A node with a single child always has it on the left.

The function recoverFromPreorder receives that string, traversal, and rebuilds the tree. It returns the root as a TreeNode?. The class has an Int field value and the child fields left and right, each a TreeNode? that starts as null.

For "1-2--3--4-5--6--7", the root is 1. The nodes -2 and -5 have one dash, so they are the root's children. The nodes --3 and --4 follow 2 and have two dashes, so they are its children, and --6 and --7 are the children of 5. The tests print this tree level by level as [1,2,5,3,4,6,7].

Values can have several digits, up to 1,000,000,000, and the tree has up to 1,000 nodes.

Approach: keep the path from the root as a stack

The string is read once, left to right. For each node, the dashes give its depth, and the digits give its value. The question is who the parent is.

In preorder, the parent of a node at depth d is the most recent node at depth d - 1. So the solution keeps a stack of the nodes on the path from the root down to the last node made. The node at position d of the stack has depth d.

For each new node at depth depth:

Pop nodes while the stack holds more than depth of them. What is left is the path down to depth depth - 1, and its top is the parent. The popped nodes are finished: their subtrees are complete, and they stay attached to their own parents.
Attach the new node to the parent. Preorder writes the left subtree first, so a parent's first child goes on the left. If the left child is already taken, the new node is the right child.
Push the new node, because the next node may be its child.

Take "1-2--3---4-5". The node 1 is pushed with no parent. The node 2 has depth 1, so the stack keeps 1 and 2 becomes its left child. Then 3 (depth 2) goes under 2, and 4 (depth 3) under 3. Now 5 has depth 1, so the stack is cut down to just the root, and 5 becomes the root's second child, its right child.

Step by step

Create stack, a new ArrayDeque<TreeNode> in a val. Its last element is the top.
Create i with var, starting at 0: the position being read in traversal.
Loop while i < traversal.length. Each pass reads one node: its dashes, then its value.
Create depth with var, starting at 0.
Loop while traversal[i] == '-'. No bounds check is needed, because the string never ends with a dash: a value always follows.
Add 1 to depth and 1 to i inside that loop. When it stops, i is on the first digit.
Create value with var, starting at 0. The number is built from its digits.
Loop while i is inside the string and traversal[i] != '-'. A value ends where the next node's dashes begin, or at the end of the string.
Append the digit: value = value * 10 + (traversal[i] - '0'), then advance i. Reading 4 and then 0 gives 4, then 4 * 10 + 0 = 40.
Create node as a TreeNode holding value.
Loop while stack.size > depth. This drops the nodes that are deeper than the parent.
Pop with removeLast() inside that loop.
Check stack.isNotEmpty(). Only the root finds an empty stack, because it is the first node and the only one at depth 0.
Name the parent: val parent = stack.last(). It stays on the stack, since it may get a second child later.
If parent.left is null, set parent.left to node.
Otherwise, set parent.right to node. A parent has at most two children, and the second one is on the right.
Push node with addLast. It is now the deepest node of the path.
Return stack.first(). The root is the first node read and is never popped, because every other node has depth 1 or more, so the stack is never cut below one element.

The solution in Kotlin

class Solution {
    fun recoverFromPreorder(traversal: String): TreeNode? {
        val stack = ArrayDeque<TreeNode>()
        var i = 0
        while (i < traversal.length) {
            var depth = 0
            while (traversal[i] == '-') {
                depth++
                i++
            }
            var value = 0
            while (i < traversal.length && traversal[i] != '-') {
                value = value * 10 + (traversal[i] - '0')
                i++
            }
            val node = TreeNode(value)
            while (stack.size > depth) {
                stack.removeLast()
            }
            if (stack.isNotEmpty()) {
                val parent = stack.last()
                if (parent.left == null) {
                    parent.left = node
                } else {
                    parent.right = node
                }
            }
            stack.addLast(node)
        }
        return stack.first()
    }
}

The Kotlin details worth a closer look:

Digits from characters. traversal[i] is a Char. Subtracting one Char from another gives an Int, so '7' - '0' is 7. Adding a Char straight to value would not give the digit.
Char literals. '-' in single quotes is a Char. traversal[i] == '-' compares two characters. Comparing with the string "-" would not compile.
The value limit. The biggest value, 1,000,000,000, is below the Int maximum of 2,147,483,647, so value never overflows.
TreeNode? as the return type. The function returns stack.first(), a non-null TreeNode, which is accepted where a nullable type is expected. first() throws on an empty deque, but the string always holds at least the root.
No null checks on the parent. stack.last() returns a TreeNode, not a TreeNode?, so parent can be used directly once the isNotEmpty() check has passed.

Complexity

Let n be the length of the string.

Time: O(n). The index i only moves forward, so every character is read once. Every node is pushed once and popped at most once.

Space: O(h) for the stack, where h is the height of the tree, since the stack holds one root-to-node path. The tree being returned takes O(n) memory, which is unavoidable.

Edge cases and common mistakes

A single node. "7" gives a tree with only the root.
Several digits. "5-12--7---40--9" has the values 5, 12, 7, 40 and 9. The node 12 is the only child of 5, so it goes on the left. The node 9 follows 40 at depth 2, so the stack is cut back to 5 and 12, and 9 becomes the right child of 12. The tests print this as [5,12,null,7,9,40].
Jumping up several levels. In "1-2--3---4-5--6---7", the node 5 follows 4 (depth 3) at depth 1. The loop pops three nodes at once. The result prints as [1,2,5,3,null,6,null,4,null,7].
Depth stays the same. In "1-2-3", the nodes 2 and 3 both have depth 1. The stack is cut to the root, 2 is the left child and 3 the right child.
Reading values one digit at a time. Treating each digit as its own node splits 12 into 1 and 2.
Forgetting to pop. If the stack isn't cut to depth, the parent would be the last node pushed, and all nodes would end up in one chain.
Putting a lone child on the right. The statement puts it on the left. Checking parent.left == null first does this.

Testing

The tests show each tree level by level, with null for missing children.

"1-2--3--4-5--6--7" gives [1,2,5,3,4,6,7].
"1-2--3---4-5--6---7" gives [1,2,5,3,null,6,null,4,null,7].
"5-12--7---40--9" gives [5,12,null,7,9,40].
"7" gives [7].
"1-2-3" gives [1,2,3].
"1-2--3-4" gives [1,2,4,3].

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

Start learning free