Problem overview
A binary tree has been 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 and no dashes, its children have one dash, and so on. 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. Values are between 1 and 1,000,000,000, so they can have several digits, and the string is always a valid walk.
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 child. The nodes --3 and --4 follow 2 and are its children. The nodes --6 and --7 follow 5. The tree is [1, 2, 5, 3, 4, 6, 7] in level order.
For "1-2--3---4-5--6---7", after ---4 at depth 3 comes -5 at depth 1. The depth drops by two at once, so 5 is the second child of the root. The result is [1, 2, 5, 3, null, 6, null, 4, null, 7].
Approach: keep the path from the root
Preorder writes a node right after its parent's earlier subtrees, so a node's parent is always the closest earlier node that is one level shallower. All we need to know while reading is the current path from the root down to the last node created.
That path is a stack. Position d of the stack holds the node at depth d. When a new node arrives with depth d:
- The nodes at positions
dand deeper are finished: preorder has left their subtrees behind. Remove them. - The top of the stack is now the node at depth
d - 1, the parent. Attach the new node to it. - Push the new node, which now ends the path.
Attaching is simple because of the order. A parent's first child is its left child, as preorder writes the left subtree first, and a single child is a left child by the statement's rule. If the left slot is already taken, the node is the second child, so it goes to the right.
On "5-12--7---40--9": 5 is the root. -12 has depth 1, so its parent is 5, and it becomes the left child. --7 goes under 12, ---40 under 7. Then --9 has depth 2: the stack, which was [5, 12, 7, 40], is cut back to [5, 12], and 9 becomes the right child of 12, because 12's left slot is taken by 7.
Step by step
- Create
stack, an empty list for the path from the root. - Create
iat 0. It is the position being read, and it only moves forward, so the string is read once. - Loop while
i < len(traversal). Each pass reads one node: its dashes, then its digits. - Start
depthat 0 for the current node. - Count the dashes with a loop that runs while
traversal[i]is'-'. It needs no bounds check, because a value always follows the dashes. - In that loop, add 1 to
depthand moveion. When it stops,iis on the first digit. - Start
valueat 0. The number is built digit by digit. - Read the digits while
iis inside the string and the character isn't a dash. Here the bounds check is needed, because the last number ends the string. - Append each digit: multiply
valueby 10, addint(traversal[i])and movei. Reading 4 and then 0 gives 4, then 40. - Create
nodeas aTreeNodeholdingvalue. - Cut the stack back with a loop that runs while
len(stack) > depth. - Pop in that loop. The removed nodes stay attached to their own parents.
- Check
if stack. Only the root finds the stack empty. - Name the top
parent, which isstack[-1]. It stays on the stack because it may get a second child. - If
parent.left is None, setparent.lefttonode. - Otherwise, set
parent.righttonode. - Push
node. It is the deepest node of the path now. - Return
stack[0]. The root is never popped, because every other node has depth 1 or more.
The solution in Python
class Solution:
def recoverFromPreorder(self, traversal: str) -> TreeNode:
stack = []
i = 0
while i < len(traversal):
depth = 0
while traversal[i] == '-':
depth += 1
i += 1
value = 0
while i < len(traversal) and traversal[i] != '-':
value = value * 10 + int(traversal[i])
i += 1
node = TreeNode(value)
while len(stack) > depth:
stack.pop()
if stack:
parent = stack[-1]
if parent.left is None:
parent.left = node
else:
parent.right = node
stack.append(node)
return stack[0]
The Python details worth a closer look:
- Strings are read by index.
traversal[i]is a one-character string, so it is compared with'-'and turned into a number withint(...). Callinginton a single digit character is safe here, because only digits can appear outside dashes. - Short-circuit order. In
i < len(traversal) and traversal[i] != '-', the bounds check comes first. Reversed, the last digit would be followed by anIndexErroron the next test. In the dash loop the order doesn't matter, because a dash is always followed by a digit. is None. Compare withNoneusingis, which tests identity. A missing child is the valueNone.- The stack is a plain list.
stack[-1]reads the last element,pop()removes it andappendadds one.stack[0]is the first element, the root. - Only the stack changes shape. Popping a node doesn't remove it from the tree, since its parent's
leftorrightstill refers to it. Python keeps the node alive as long as something refers to it.
Complexity
Time: O(n), where n is the length of the string. The index i only moves forward, so each character is read once. Every node is pushed once and popped at most once, so the stack work is bounded by the number of nodes, which is at most the length of the string.
Space: O(h) for the stack, where h is the height of the tree, plus the tree itself. The stack holds one root-to-node path. A chain of 1000 nodes gives a stack of 1000 entries.
Edge cases and common mistakes
- A single node.
"7"reads depth 0 and value 7, finds an empty stack and pushes the root. The result is a tree with just 7. - Multi-digit values. In
"5-12--7---40--9", the digit loop reads 12 and 40 whole. Treating each character as a value would produce wrong nodes. - A single child is a left child.
"5-12"puts 12 on the left of 5, never on the right. - The depth can drop by several levels. That is why the stack is cut with a loop instead of one
pop(). - Dashes and the root. For
"1-2-3", both 2 and 3 have depth 1. After 2 is read, the stack is cut back to [1], so 3 becomes the right child of 1. - Popping to the wrong size. Cutting to
depth + 1ordepth - 1attaches the node to the wrong parent. The stack must have exactlydepthentries before the node is attached. - Returning the last node. The last node pushed is a leaf. The root is
stack[0], because it never gets popped.
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]."1-2-3"gives[1, 2, 3].
