Problem overview
A binary tree is written as a string in preorder: first a node, then its whole left subtree, then its whole 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. If a node has only one child, that child is the left one.
The method recoverFromPreorder receives traversal, such as "1-2--3--4-5--6--7", and returns the root of the rebuilt TreeNode. A TreeNode has an Int field value and the fields left and right, which are null when a child is missing. The tree has between 1 and 1000 nodes, with values from 1 to 1,000,000,000.
For "1-2--3--4-5--6--7", the root is 1. The nodes with one dash, 2 and 5, are its children, and 2 comes first, so it is the left one. The nodes --3 and --4 come right after 2, so they are its children, and --6 and --7 are the children of 5. For "5-12--7---40--9" the values can have several digits: the dashes before a node end where its digits start. The root 5 has only one child, 12, which goes on the left.
Approach: keep the path from the root to the newest node
Preorder has a useful property: when a node is written, its parent is the most recently written node that is exactly one level above it, and everything the string wrote in between belongs to finished subtrees. So the code only needs to remember the current path from the root down to the last node it created.
Keep that path on a stack, with the root at the bottom. Position d of the stack then holds the node of depth d. Read the string from left to right, one node at a time:
- Count the dashes: that is the new node's depth
d. - Read the digits: that is the value.
- The path may be deeper than
d, because the previous node can be deeper. Pop nodes until the stack holds exactlydnodes. The top is then the node at depthd - 1, the parent. - Attach the new node to that parent: as the left child if the left slot is free, otherwise as the right child. Preorder writes the left subtree first, so a parent's first child is always its left child.
- Push the new node, since the next one may be its child.
Popped nodes are not lost. Each one stays attached to its own parent, so only the path is forgotten, not the tree.
For "1-2--3---4-5--6---7" the stack goes like this. After 1, the stack is [1]. After -2 it is [1, 2], and 2 is the left child of 1. After --3 it is [1, 2, 3], and after ---4 it is [1, 2, 3, 4]. Then -5 has depth 1: pop until one node is left, [1], and 1 already has a left child, so 5 becomes its right child, and the stack is [1, 5]. The rest, 6 and 7, goes down the left side of 5. The tree is [1, 2, 5, 3, null, 6, null, 4, null, 7] in level order.
Step by step
- Create the stack in a
val: an emptyArrayBuffer[TreeNode], used as a stack whose last element is the top. - Declare
iwithvar, the reading position, starting at 0. Every loop that reads a character moves it forward, so the string is read once. - Loop while
i < traversal.length. Each pass reads one node: its dashes, then its value. - Start
depthat 0 withvar. It counts this node's dashes. - Loop while
traversal(i) == '-'. No bounds check is needed: a value always follows the dashes, so the string never ends on a dash. - Count and move. Add 1 to
depthandi += 1. Scala has no++operator. When the loop stops,iis on the first digit. - Start
valueat 0 withvar. The number is built digit by digit. - Loop over the digits while
iis inside the string andtraversal(i) != '-'. The value ends at the next dash or at the end of the string. - Add the digit.
value = value * 10 + (traversal(i) - '0'), theni += 1. Reading 4 and then 0 gives 4, then 4 * 10 + 0 = 40. - Create the node with
new TreeNode(value)in aval. - Trim the path. Loop while
stack.length > depth. - Pop the top inside it with
stack.remove(stack.length - 1). Afterwards the stack holds the path down to depthdepth - 1. - Skip the root. An
if (stack.nonEmpty)guards the next lines, since only the root, the first node, finds an empty stack. - Name the parent as
stack.last. It stays on the stack, because it may get a second child later. - Left if free. If
parent.left == null, setparent.left = node. - Otherwise right. In the
elsebranch, setparent.right = node. - Push the node with
stack += node. - Return
stack(0)after the loop. The root is never popped, so it is at the bottom.
The solution in Scala
class Solution {
def recoverFromPreorder(traversal: String): TreeNode = {
val stack = scala.collection.mutable.ArrayBuffer[TreeNode]()
var i = 0
while (i < traversal.length) {
var depth = 0
while (traversal(i) == '-') {
depth += 1
i += 1
}
var value = 0
while (i < traversal.length && traversal(i) != '-') {
value = value * 10 + (traversal(i) - '0')
i += 1
}
val node = new TreeNode(value)
while (stack.length > depth) {
stack.remove(stack.length - 1)
}
if (stack.nonEmpty) {
val parent = stack.last
if (parent.left == null) {
parent.left = node
} else {
parent.right = node
}
}
stack += node
}
return stack(0)
}
}
The Scala details worth knowing:
- Indexing a
String.traversal(i)returns theCharat positioni. Characters are compared with==against a character literal in single quotes,'-'. - Char minus Char is an Int.
'7' - '0'is theInt7, because the digit characters have consecutive codes. That is what turns a digit character into its number. - No
++. Scala has no increment operator, so usei += 1. - Int is enough. The largest value, 1,000,000,000, is below the
Intlimit of 2,147,483,647, andvalue * 10is computed before the last digit is added, so it never exceeds the final value. ArrayBufferas a stack.+=appends at the end,lastreads the top,remove(index)deletes an element, andstack(0)reads the bottom.laston an empty buffer throws, so thenonEmptycheck comes first.- Fields and
null.parent.left == nullasks whether the slot is still empty. A new node starts with both childrennull. return stack(0). The method could also end with juststack(0). Both give the same result.
Complexity
Let n be the length of the string.
Time: O(n). The reading position only moves forward, so every character is looked at once. Each node is pushed once and popped at most once, so the trimming loop costs at most one pop per node over the whole run.
Space: O(h) extra for the stack, where h is the height of the tree, since the stack holds one root-to-node path. The tree itself takes O(n) memory, and it is the result.
Edge cases and common mistakes
- One node.
"8"has no dashes. The root is created, the stack is empty so no parent is attached, and the method returns it. - Multi-digit values.
"5-12--7---40--9"has the values 12 and 40. Reading one character per node would produce the wrong tree, which is why the digits are read in a loop. - The depth drops by more than one level. After
---4comes-5in the second example. The trimming loop pops three nodes in one go, which a single pop would miss. - A single child goes left. The root of
"5-12--7---40--9"has one child, 12, and the code puts it inparent.leftbecause the left slot is empty. In"1-2-3"the root has two children: 2 on the left and 3 on the right. - A node that goes back up to a shallower parent. In
"1-2--3-4"the node 4 has depth 1, so it attaches to the root. The root's left is already 2, so 4 goes right. The level order is[1, 2, 4, 3]. - Taking the depth from the stack. The depth comes from the dashes. The stack is only trimmed down to that size, never grown to it, so a node can't be attached to a level that doesn't exist.
- Confusing a dash with a minus sign. Values are positive, so a dash never belongs to a number. Every dash is a depth marker.
- Not advancing
iin an inner loop. The loop would never end. All three read loops moveiin their body.
Testing
Trees are shown in level order, with null for missing children and trailing nulls left out.
"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-3"gives[1, 2, 3]."1-2--3-4"gives[1, 2, 4, 3]."1000000000-5"gives[1000000000, 5].
