Start learning free

LESSON 347 OF 437 · BINARY TREES

Recover a Tree From Preorder Traversal in C++: Stack of the Path

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 109.
  • traversal is a valid preorder walk of a tree, written as described above.
STEP 1 OF 18
    Ctrl + Enter to check

    C++ · BINARY TREES

    Recover Tree From Preorder in C++, explained

    Problem overview

    The function recoverFromPreorder receives a string traversal that describes a binary tree in preorder: each node is written as its depth in dashes followed by its value. The root has depth 0, so it has no dashes. If a node has only one child, that child is the left one. The function rebuilds the tree and returns its root.

    For "1-2--3--4-5--6--7" the nodes are 1 (depth 0), 2 (depth 1), 3 and 4 (depth 2), 5 (depth 1), 6 and 7 (depth 2). Node 2 is the first node at depth 1, so it is the root's left child; 3 and 4 follow it directly, so they are the children of 2. Node 5 is the root's right child, with children 6 and 7. The result prints as [1,2,5,3,4,6,7].

    Values are not single digits: in "5-12--7---40--9" the value 12 has two digits, and the dashes before the next number end where its digits start.

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

    Preorder writes a node, then its whole left subtree, then its whole right subtree. So when a node at depth d appears, its parent is the most recent node at depth d - 1. Everything deeper that came before has been finished: those nodes can't get more children, because the walk has already come back up.

    That suggests a stack holding the current path, with the node at position d having depth d. To place a new node at depth d:

    1. Drop nodes from the top until the stack holds exactly d nodes. Its top is then the parent.
    2. Attach the new node to the parent: as the left child if the parent has none yet, otherwise as the right child.
    3. Push the new node, since its own children may come next.

    The string is read once from left to right, so the work is linear in its length.

    On "1-2--3---4-5--6---7": after 1, 2, 3 and 4 the stack is [1, 2, 3, 4]. Next comes 5 at depth 1, so three nodes are popped down to [1], and 5 becomes the root's second child, its right child. Then 6 goes to the left of 5, and 7 on the left of 6. The output is [1,2,5,3,null,6,null,4,null,7].

    Step by step

    1. Create the stack as a vector<TreeNode *>, using push_back, pop_back and back() as stack operations.
    2. Keep a reading position i, starting at 0.
    3. Loop while i is inside the string. Each pass reads one node: its dashes, then its digits.
    4. Start a depth counter at 0 for this node.
    5. Count the dashes with a loop that runs while the current character is '-'.
    6. Advance in that loop: add one to depth and move i on. When it stops, i is at the first digit.
    7. Start the value at 0.
    8. Read the digits with a loop that runs while i is inside the string and the character isn't a dash.
    9. Add each digit to the end of the number: multiply value by 10, then add traversal[i] - '0'. Reading 4 and then 0 gives 4, then 40.
    10. Create the node with new TreeNode(value).
    11. Drop the deeper nodes while the stack holds more than depth nodes.
    12. Pop them with pop_back(). They stay attached to their own parents.
    13. Check that the stack is not empty. Only the root, the first node read, finds it empty.
    14. Read the parent with stack.back(). It stays on the stack, because it may get a second child later.
    15. Left child first: if parent->left is still NULL, the new node becomes the left child.
    16. Otherwise right: the left child is taken, so the new node is the right child.
    17. Push the new node onto the stack.
    18. Return stack[0]. The root is the first node pushed and is never popped, since every later node has depth 1 or more.

    The solution in C++

    class Solution {
public:
    TreeNode* recoverFromPreorder(string traversal) {
        vector<TreeNode *> stack;
        int i = 0;
        while (i < traversal.size()) {
            int depth = 0;
            while (traversal[i] == '-') {
                depth++;
                i++;
            }
            int value = 0;
            while (i < traversal.size() && traversal[i] != '-') {
                value = value * 10 + (traversal[i] - '0');
                i++;
            }
            TreeNode *node = new TreeNode(value);
            while (stack.size() > depth) {
                stack.pop_back();
            }
            if (!stack.empty()) {
                TreeNode *parent = stack.back();
                if (parent->left == NULL) {
                    parent->left = node;
                } else {
                    parent->right = node;
                }
            }
            stack.push_back(node);
        }
        return stack[0];
    }
};

    The C++ details worth a closer look:

    • Characters are numbers. traversal[i] - '0' works because the digit characters are consecutive, so '7' - '0' is the int 7. A char is promoted to int in the subtraction.
    • The dash loop has no bounds check. The string never ends with a dash, so i stops at a digit. For a std::string, reading traversal[traversal.size()] is also allowed and gives '\0', so even a read at the end is safe.
    • Signed and unsigned. i and depth are int, while size() is unsigned. Comparing them converts the int to unsigned. That is harmless here because neither can be negative, but a compiler with warnings on will mention it.
    • Value range. Values go up to 1,000,000,000, which fits in an int (maximum 2,147,483,647). value * 10 is computed before the last digit is added, and for a number of up to 1,000,000,000 the largest intermediate is 1,000,000,000 itself, so it never overflows.
    • The vector as a stack. vector has no top(); back() reads the last element. A vector also gives stack[0] access to the bottom, which std::stack doesn't allow, and that is how the root is returned.
    • The nodes are never freed. Each new allocates a node that the returned tree owns. Releasing it is the caller's job.

    Complexity

    Time: O(m), where m is the length of the string. Each character is read once. Each node is pushed once and popped at most once, so all the stack work together is linear in the number of nodes, which is at most m.

    Space: O(h) for the stack, where h is the height of the tree, on top of the nodes of the tree being built.

    Edge cases and common mistakes

    • A single node. "1000000000" has no dashes. The stack is empty, so no parent is looked up, and the function returns that node.
    • Several digits. Reading only one character per node breaks on 12 or 40. The digits loop stops at a dash or at the end of the string.
    • Jumping up several levels. After a deep node, a node at a much smaller depth pops many entries at once. That is why the code uses a while loop, not a single pop_back().
    • Single children. The statement says a lone child is a left child. The code does this naturally: the left slot is always filled first.
    • Using stack.size() >= depth. That would pop one node too many and attach the node to the wrong parent.
    • Popping the parent too early. Popping the parent after its first child would make the second child impossible to attach.

    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].
    • "1000000000" gives [1000000000].
    • "1-2" gives [1,2].
    Keep going with C++About 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free