Start learning free

LESSON 348 OF 438 · BINARY TREES

Recover a Tree From Preorder Traversal in Java: One Pass 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

JAVA · BINARY TREES

Recover Tree From Preorder in Java, explained

Problem overview

A binary tree is written in preorder as a string: each node appears as its depth in dashes followed by its value, in the order node, left subtree, right subtree. The root has depth 0 and no dashes. If a node has only one child, that child is the left one. The method recoverFromPreorder receives the string traversal and returns the root of the rebuilt tree.

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

In "1-2--3---4-5--6---7", after ---4 at depth 3 comes -5 at depth 1. The depth drops by two levels at once, so 5 is the second child of the root, the right one. In "5-12--7---40--9", values can have several digits: the dashes before a node end where its digits start.

Approach: keep the path from the root to the last node

Preorder writes a node right after its parent's earlier subtrees, so the string can be read once from left to right. The key observation is about the path from the root to the node just created. The node at position d on that path has depth d.

When the next node is read with depth d, its parent is the node at depth d - 1 on the path. Everything deeper than that is finished: those subtrees are complete and stay attached to their own parents. So the algorithm keeps a stack that holds this path, and for each new node it does three things:

Pop nodes until the stack holds exactly d nodes. Now its top is the new node's parent.
Attach the new node to that parent: as the left child if the parent has none yet, otherwise as the right child.
Push the new node, since it extends the path and could be the parent of the next one.

The first node, at depth 0, meets an empty stack and becomes the root. It is never popped, because every later node has depth 1 or more, so the stack never drops below one node.

Step by step

Create a Stack<TreeNode> for the path from the root to the newest node.
Keep a read position i, starting at 0. Every loop that reads characters advances it, so the string is read once.
Loop while i < traversal.length(). Each pass reads one node: its dashes and then its digits.
Start depth at 0. It will count this node's dashes.
Count the dashes with a loop that runs while traversal.charAt(i) is '-'. It needs no bounds check, because a valid string never ends in a dash.
Increase depth and move i forward inside that loop. When it stops, i is on the first digit.
Start value at 0. The number is built digit by digit.
Loop over the digits while i is inside the string and the character isn't a dash. The value ends at the next node's dashes or at the end of the string.
Append each digit: multiply value by 10 and add traversal.charAt(i) - '0', then advance i. Reading 4 and then 0 gives 4 * 10 + 0 = 40.
Create the node as new TreeNode(value).
Pop while stack.size() > depth to drop the finished nodes.
Pop inside that loop. The popped nodes keep their links to their own parents.
If the stack isn't empty, a parent exists. Only the root has none.
Read the parent with stack.peek(). It doesn't remove it, because the parent may get a second child later.
Left first: if parent.left == null, the new node is the left child.
Otherwise it is the right child. A parent has at most two children, and the second is always on the right.
Push the new node. It is now the deepest node of the path.
Return stack.get(0) after the loop. The bottom of the stack is the root.

The solution in Java

class Solution {
    public TreeNode recoverFromPreorder(String traversal) {
        Stack<TreeNode> stack = new Stack<>();
        int i = 0;
        while (i < traversal.length()) {
            int depth = 0;
            while (traversal.charAt(i) == '-') {
                depth++;
                i++;
            }
            int value = 0;
            while (i < traversal.length() && traversal.charAt(i) != '-') {
                value = value * 10 + (traversal.charAt(i) - '0');
                i++;
            }
            TreeNode node = new TreeNode(value);
            while (stack.size() > depth) {
                stack.pop();
            }
            if (!stack.isEmpty()) {
                TreeNode parent = stack.peek();
                if (parent.left == null) {
                    parent.left = node;
                } else {
                    parent.right = node;
                }
            }
            stack.push(node);
        }
        return stack.get(0);
    }
}

Java details worth a closer look:

Characters are numbers. traversal.charAt(i) is a char, and subtracting '0' gives an int: '7' - '0' is 7. Adding the char to value without subtracting would add its character code (55 for '7').
Chars compare with ==. A char is a primitive, so traversal.charAt(i) == '-' is correct. Single quotes mean a char, and double quotes mean a String.
Stack is also a list. java.util.Stack extends Vector, so get(0) reads the bottom element and size() counts the nodes. peek() reads the top without removing it. A Deque such as ArrayDeque has no get(int).
The order of the two conditions in the digit loop matters. i < traversal.length() comes first, so charAt is never called past the end of the string, which would throw a StringIndexOutOfBoundsException.
Values reach one billion. The largest allowed value, 1,000,000,000, fits in an int, whose maximum is 2,147,483,647, so value * 10 + digit doesn't overflow.

Complexity

Time: O(n), where n is the length of the string. Every character is read once. Each node is pushed once and popped at most once, so the pops add only O(number of nodes) in total, even though one pass can pop many nodes.

Space: O(h) for the stack, where h is the height of the tree, plus the tree itself, which is the output. In the worst case, a chain of nodes, the height equals the number of nodes.

Edge cases and common mistakes

A single node. "7" reads depth 0 and value 7, finds an empty stack, pushes the node and returns it.
Several digits. Reading one character as one value turns "5-12--7" into nodes 1 and 2. The digit loop runs until the next dash.
Depth jumping up by more than one. Popping a single node per new node would leave the wrong parent in "1-2--3---4-5". Popping while stack.size() > depth handles any jump.
A node with a single child. It must be the left child, which is why the code fills left before right. In "5-12--7---40--9", the root 5 has 12 as its left child and nothing on the right.
Using pop() instead of peek() for the parent. That removes the parent, and a second child would have no parent to attach to.
Returning the top of the stack instead of the bottom. After the loop the top is the last node read, not the root.

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].
"7" gives [7].

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

Start learning free