Start learning free

LESSON 353 OF 443 · BINARY TREES

Recover a Tree From Preorder Traversal in Swift: Path Stack, O(n)

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

    SWIFT · BINARY TREES

    Recover Tree From Preorder in Swift, explained

    Problem overview

    A binary tree is written as a string in preorder: each node comes as its depth in dashes followed by its value, in the order node, left subtree, right subtree. The root has depth 0, so it has 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, a TreeNode?.

    For "1-2--3--4-5--6--7" the tree has root 1. The nodes with one dash, 2 and 5, are its children, 2 on the left. The two-dash nodes after -2 (3 and 4) belong to 2, and the two after -5 (6 and 7) belong to 5. In level order that is [1, 2, 5, 3, 4, 6, 7]. For "5-12--7---40--9" values can have several digits, and the tree is [5, 12, null, 7, 9, 40]: 5 has the single left child 12, and 12 has the children 7 and 9, with 40 under 7.

    Approach: keep the path from the root

    The string is in preorder, so a node's parent is always the nearest earlier node whose depth is one less. Keep a stack of the nodes on the path from the root down to the node just created, where the node at position d of the stack has depth d. For a new node at depth d:

    • Pop the stack until it holds exactly d nodes. Those popped are finished: their subtrees are complete, and they stay attached to their own parents.
    • The top of the stack is now the parent. If it has no left child yet, the new node becomes its left child; otherwise it becomes its right child. A parent's first child is the left one, since the left subtree is written first, and a lone child is left by the problem's rule.
    • Push the new node: it is now the deepest node on the path.

    On "1-2--3---4-5": the stack builds up 1, 2, 3, 4 as the depths 0, 1, 2, 3 arrive. Then -5 has depth 1. Popping down to one node leaves just node 1 on the stack. Node 1 already has the left child 2, so 5 becomes its right child. Reading the string once, with a stack, takes linear time.

    Step by step

    1. Turn the string into an array of characters with Array(traversal), stored in a let named chars. A Swift string can't be read by an integer index.
    2. Create the path stack, a var of type [TreeNode].
    3. Create i, the reading position, at 0. It only moves forward, so the string is read once.
    4. Loop while i < chars.count. Each pass reads one node: its dashes and then its digits.
    5. Start depth at 0 to count this node's dashes.
    6. Loop while chars[i] == "-". No bounds check is needed: a dash is always followed by a value.
    7. Count each dash by adding 1 to depth and moving i on. When the loop stops, i is on the first digit.
    8. Start value at 0 to build the number from its digits.
    9. Loop while i is in range and chars[i] != "-". The value ends at the next dash or at the end of the string.
    10. Add each digit: multiply value by 10, add chars[i].wholeNumberValue!, and move i on.
    11. Create the node with TreeNode(value) in a let.
    12. Drop the deeper nodes: loop while stack.count > depth.
    13. Remove the top with removeLast().
    14. Find the parent with if let parent = stack.last. For the root the stack is empty, and the block is skipped.
    15. Left first: if parent.left == nil, set parent.left = node.
    16. Otherwise right: the parent already has a left child, so the node goes to parent.right.
    17. Push the node. It may become a parent soon.
    18. Return stack[0]. The root is the first node read, and it is never popped, because every later node has depth 1 or more.

    The solution in Swift

    class Solution {
    func recoverFromPreorder(_ traversal: String) -> TreeNode? {
        let chars = Array(traversal)
        var stack: [TreeNode] = []
        var i = 0
        while i < chars.count {
            var depth = 0
            while chars[i] == "-" {
                depth += 1
                i += 1
            }
            var value = 0
            while i < chars.count && chars[i] != "-" {
                value = value * 10 + chars[i].wholeNumberValue!
                i += 1
            }
            let node = TreeNode(value)
            while stack.count > depth {
                stack.removeLast()
            }
            if let parent = stack.last {
                if parent.left == nil {
                    parent.left = node
                } else {
                    parent.right = node
                }
            }
            stack.append(node)
        }
        return stack[0]
    }
}

    Swift details worth knowing:

    • Character and wholeNumberValue. chars[i] is a Character, not an integer. wholeNumberValue gives the number it shows as an Int?: Character("7").wholeNumberValue is 7, and a non-digit like "x" gives nil. The ! is safe here because the loop only reads characters that are not dashes, so they are digits.
    • Classes let you change a let. parent is a constant from if let, but TreeNode is a class, so parent.left = node changes the node itself and not only a copy.
    • Comparing with nil. parent.left == nil works for an optional of any type, even though TreeNode doesn't conform to Equatable.
    • if let on stack.last. last is an optional, nil for an empty array, so the root case needs no special check.
    • Large values. Values go up to 10^9, and value * 10 + digit stays below 10^10, which fits easily in a 64-bit Int.

    Complexity

    Time: O(n), where n is the length of the string. The index i only moves forward, and every node is pushed once and popped at most once.

    Space: O(h) for the stack, plus the tree itself, which has to be built. The stack holds the path from the root to the newest node, never more than the height of the tree.

    Edge cases and common mistakes

    • A single node. "7" reads depth 0 and value 7, creates the root, and returns it.
    • Several digits. "5-12--7" must read 12 as one value. Treating each digit as a node would break the tree. The digits loop ends only at a dash or the end of the string.
    • A big jump up. In "1-2--3---4-5" the depth falls from 3 to 1. Popping down to depth nodes handles any jump in one loop.
    • Single children are left. "1-2" gives the tree [1, 2] with 2 on the left, and "1-2--3---4----5" is a chain of left children: [1, 2, null, 3, null, 4, null, 5].
    • Large values. "1000000000-999999999--1" has two values near 10^9, and they are parsed exactly.
    • Looking at the end of the string. In the dashes loop chars[i] is read without a bounds check, which is fine for valid input. In the digits loop the check i < chars.count comes first, so it can't read past the end.
    • Attaching to the wrong parent. Using the last created node as the parent, instead of the node at depth depth - 1, breaks as soon as the depth goes back up.

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