Start learning free

LESSON 352 OF 442 · BINARY TREES

Recover a Tree From Preorder Traversal in TypeScript: Stack by Depth

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

TYPESCRIPT · BINARY TREES

Recover Tree From Preorder in TypeScript, explained

Problem overview

The method recoverFromPreorder receives traversal, a string that describes a binary tree walked in preorder: a node, then its left subtree, then its right subtree. Each node is written as D dashes followed by its value, where D is the node's depth. The root has depth 0, so it has no dashes. When a node has just one child, that child is the left one. The method rebuilds the tree and returns its root.

In "1-2--3--4-5--6--7", the nodes 2 and 5 have one dash, so they are the root's children, with 2 on the left. Then 3 and 4 follow 2 with two dashes, so they are its children, and 6 and 7 are the children of 5. The tree level by level is [1, 2, 5, 3, 4, 6, 7].

In "5-12--7---40--9", values can have several digits: 12 is one value, and the dashes after it start the next node. The tree is [5, 12, null, 7, 9, 40]: 5 has only the left child 12, which has children 7 and 9, and 7 has the left child 40.

Approach: keep the path from the root

Preorder writes every node right after its parent's earlier nodes, so while reading, the only nodes that can still receive children are those on the path from the root down to the node most recently read. A stack can hold exactly that path. The node at position d of the stack has depth d.

When a new node with depth depth is read, its parent is the node at depth depth - 1. Anything deeper on the stack belongs to a branch that has been finished, so pop until the stack has exactly depth entries. Then the top is the parent. The node becomes its left child if that is free, and otherwise its right child, since preorder writes the left subtree first. Finally the node is pushed, because its own children may come next.

On "1-2--3---4-5--6---7", after reading ---4 the stack is 1, 2, 3, 4. The next node, -5, has depth 1, so the stack is popped down to just 1. Node 1 already has the left child 2, so 5 becomes its right child. Nodes 6 and 7 follow in the same way, with each being the left child, since each has no sibling. The tree is [1, 2, 5, 3, null, 6, null, 4, null, 7].

Step by step

Create stack, an empty TreeNode[], holding the path to the latest node.
Create i, the reading position, starting at 0.
Loop while i < traversal.length. Each pass reads one node: its dashes, then its value.
Create depth at 0 for this node's dash count.
Loop over the dashes while traversal[i] === '-'. A value always follows the dashes, so no length check is needed.
Count each dash by adding one to depth and moving i on.
Create value at 0 to build the number.
Loop over the digits while i is inside the string and the character is not a dash. This time the length check matters, because the last value ends the string.
Add each digit: value = value * 10 + Number(traversal[i]), then move i on. Reading 4 and then 0 gives 4, then 40.
Create node as new TreeNode(value).
Drop finished nodes: while stack.length > depth, pop. Afterwards the stack holds the path down to depth depth - 1.
Pop inside that loop. The dropped nodes keep their own subtrees, and they stay attached to their parents.
Check that the stack is not empty. Only the root finds it empty.
Name the top parent, at index stack.length - 1. It stays on the stack, since it may get a second child.
If parent.left is null, make node the left child.
Otherwise, make it parent.right.
Push node. It's now the deepest node on the path.
Return stack[0]. The root is the first node read and is never popped, because every other node has depth 1 or more.

The solution in TypeScript

class Solution {
    recoverFromPreorder(traversal: string): TreeNode | null {
        let stack: TreeNode[] = [];
        let i = 0;
        while (i < traversal.length) {
            let depth = 0;
            while (traversal[i] === '-') {
                depth++;
                i++;
            }
            let value = 0;
            while (i < traversal.length && traversal[i] !== '-') {
                value = value * 10 + Number(traversal[i]);
                i++;
            }
            let node = new TreeNode(value);
            while (stack.length > depth) {
                stack.pop();
            }
            if (stack.length > 0) {
                let parent = stack[stack.length - 1];
                if (parent.left === null) {
                    parent.left = node;
                } else {
                    parent.right = node;
                }
            }
            stack.push(node);
        }
        return stack[0];
    }
}

The TypeScript details to know:

Indexing a string. traversal[i] gives a one-character string. Past the end it gives undefined instead of throwing, so traversal[i] === '-' is simply false there. The dash loop needs no length check anyway, because a value always follows the dashes.
Digits to numbers. Number('4') is 4. The expression value * 10 + Number(traversal[i]) is arithmetic on numbers. Without Number, value * 10 + traversal[i] would concatenate: 4 * 10 + '0' is the string "400", not 40.
Large values. Values reach 1,000,000,000, which a number holds exactly.
The starter comment's TreeNode. The class is provided with val, left and right, and a constructor taking val that sets both children to null. That is why parent.left === null is a valid test for a free slot.
Objects are shared references. Pushing node onto the stack and attaching it to parent.left both store the same object, so changes made later through the stack, such as giving it children, show up in the tree.
The return type. It is TreeNode | null. stack[0] is a TreeNode, which fits, since the input always has at least the root.

Complexity

Time: O(n), where n is the length of traversal. The index i only moves forward, so each 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, plus the O(n) nodes of the tree being returned. For a tree shaped like a list the stack holds every node.

Edge cases and common mistakes

Only a root. "8" reads one node. The stack is empty, so there is no parent, and the result is [8].
One child. "1-2" gives [1, 2], with 2 as the left child.
Multi-digit values. "1000000000-5" gives [1000000000, 5]. Reading one character as a whole value would split 1000000000 into ten nodes.
Going up several levels. After a deep node, a node with a small depth pops many entries at once, as in the jump from depth 3 to depth 1 in the second example.
Mixing up depth and value. Dashes are only counted before a value. The loop for digits stops at the next dash, which belongs to the next node.
Popping the parent. The loop keeps depth nodes, not depth - 1, so the parent stays on the stack. Popping it would lose the place where the right child must go.
Making every node a left child. The first child goes left, but a second child must go right, which is what the else does.

Testing

"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].
"8" gives [8].
"1-2" gives [1, 2].

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

Start learning free