💡 The current_number now includes node 1's value as the first digit in the path.
compare
At node 2, check left child is null
At node 2, check if left child exists. It does not, so we will process this node as a leaf candidate.
💡 This check determines if we can form a complete root-to-leaf number at this node.
Line:if node.left is None:
💡 Leaf nodes or nodes without left children are processed directly in Morris traversal.
fill_cells
Process node 2 with no left child
At node 2, left child is null, so update current_number to 12 (1*10+2). Node 2 is a leaf, so add 12 to total. Then move to right child which is threaded link back to node 1.
💡 Processing leaf nodes is where the path number is complete and added to the total sum.
Line:if node.left is None:
current_number = current_number * 10 + node.val
if node.left is None and node.right is None:
total += current_number
node = node.right
current_number //= 10
💡 Leaf nodes finalize a root-to-leaf number which contributes to the sum.
shrink
Remove threaded link and backtrack
At node 1 again, predecessor is node 2. Since predecessor.right points to node 1, remove the threaded link, remove node 1's digit from current_number by dividing by 10, and move to right child (node 3).
💡 Removing the threaded link restores the original tree structure and backtracks the path number.
💡 Backtracking removes digits from current_number to reflect moving up the tree.
compare
At node 3, check left child is null
At node 3, check if left child exists. It does not, so we will process this node as a leaf candidate.
💡 This check determines if we can form a complete root-to-leaf number at this node.
Line:if node.left is None:
💡 Leaf nodes or nodes without left children are processed directly in Morris traversal.
fill_cells
Process node 3 with no left child
At node 3, left child is null, so update current_number to 13 (1*10+3). Node 3 is a leaf, so add 13 to total. Then move to right child which is null.
💡 Processing the right leaf node completes the second root-to-leaf path number.
Line:if node.left is None:
current_number = current_number * 10 + node.val
if node.left is None and node.right is None:
total += current_number
node = node.right
current_number //= 10
💡 The second leaf node completes the second path number contributing to the sum.
reconstruct
Traversal complete, return total sum
No more nodes to visit (node is null), so return the total sum of all root-to-leaf numbers, which is 25.
💡 The algorithm finishes by returning the accumulated sum of all root-to-leaf numbers.
Line:return total
💡 The final answer is the sum of all numbers formed from root to leaf paths.
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
class Solution:
def sumNumbers(self, root: TreeNode) -> int:
total = 0 # STEP 1
current_number = 0 # STEP 1
node = root # STEP 1
while node: # STEP 2 loop
if node.left is None: # STEP 2 check
current_number = current_number * 10 + node.val # STEP 5 update number
if node.left is None and node.right is None: # STEP 5 leaf check
total += current_number # STEP 5 add to total
node = node.right # STEP 5 move right
current_number //= 10 # STEP 5 backtrack number
else:
predecessor = node.left # STEP 3 find predecessor
steps = 1 # STEP 3 count steps
while predecessor.right and predecessor.right != node: # STEP 3 loop
predecessor = predecessor.right # STEP 3 move right
steps += 1 # STEP 3 increment steps
if predecessor.right is None: # STEP 4 create thread
predecessor.right = node # STEP 4 link
current_number = current_number * 10 + node.val # STEP 4 update number
node = node.left # STEP 4 move left
else: # STEP 6 remove thread
predecessor.right = None # STEP 6 unlink
if not node.left and not node.right: # STEP 6 leaf check
total += current_number # STEP 6 add to total
current_number //= 10 ** steps # STEP 6 backtrack number
node = node.right # STEP 6 move right
return total # STEP 8 return result
📊
Sum Root to Leaf Numbers - Watch the Algorithm Execute, Step by Step
Watching this step-by-step traversal reveals how the algorithm cleverly modifies the tree temporarily to avoid recursion, and how it accumulates path numbers only at leaf nodes.
Step 1/10
·Active fill★Answer cell
Current node: 1
123
Current node: 1
123
Current node: 1
123
Current node: 2
123
Current node: 2
123
Current node: 1
123
Current node: 3
123
Current node: 3
123
123
123
Return: 25
Key Takeaways
✓ Morris traversal uses temporary threaded links to traverse the tree without recursion or extra space.
This is hard to see from code alone because the tree structure is modified and restored dynamically.
✓ The current_number variable accumulates digits as we go down the tree and backtracks correctly when returning up.
Watching the number build and shrink visually clarifies how path numbers are formed and discarded.
✓ Leaf nodes trigger the addition of the current path number to the total sum, marking completion of a root-to-leaf path.
Seeing exactly when and why the sum updates helps understand the problem's core logic.
Practice
(1/5)
1. You need to output the values of a binary tree's nodes in the order: left subtree, node itself, then right subtree, without modifying the tree structure or using extra space proportional to the tree height. Which approach best fits this requirement?
easy
A. Use a breadth-first search (BFS) to visit nodes level by level.
B. Use a recursive preorder traversal that visits root, left, then right nodes.
C. Use Morris traversal to perform inorder traversal with O(1) extra space by temporarily modifying tree links.
D. Use a dynamic programming approach to store and reuse subtree results.
Solution
Step 1: Understand traversal order requirement
Inorder traversal visits left subtree, then node, then right subtree, matching the problem's order.
Step 2: Identify approach with O(1) space
Morris traversal achieves inorder traversal without recursion or stack by temporarily modifying tree pointers, restoring them after use.
Final Answer:
Option C -> Option C
Quick Check:
Morris traversal is known for O(1) space inorder traversal [OK]
Hint: Morris traversal enables inorder with O(1) space [OK]
Common Mistakes:
Confusing preorder with inorder traversal order
Assuming BFS can produce inorder sequence
Thinking DP applies to traversal order
2. You are given a binary tree where each node contains an integer value (which can be negative). The task is to find the maximum sum of values along any path in the tree, where a path can start and end at any node and must be connected through parent-child links. Which approach guarantees an optimal solution for this problem?
easy
A. Perform a postorder traversal with recursion, tracking the maximum gain from each subtree and updating a global maximum path sum.
B. Enumerate all possible paths in the tree and compute their sums to find the maximum.
C. Use a greedy traversal that picks the maximum child at each node and sums values along that path.
D. Use a breadth-first search (BFS) to find the longest path and sum its node values.
Solution
Step 1: Understand the problem constraints
The path can start and end at any node, not necessarily the root or leaf, and node values can be negative.
Step 2: Identify the approach that handles all cases optimally
Postorder recursion allows computing maximum gains from left and right subtrees, considering negative values by ignoring negative gains, and updating a global max path sum that includes both children and the current node.
Final Answer:
Option A -> Option A
Quick Check:
Postorder recursion with global max handles negative values and arbitrary paths [OK]
Hint: Postorder recursion tracks max gains and global max [OK]
Common Mistakes:
Greedy approach fails on negative values and non-root paths
Enumerating all paths is inefficient and impractical
BFS does not capture arbitrary path sums
3. Given the following code snippet for building a tree from inorder and postorder traversals, what is the value of inorder_index after processing the first iteration of the for-loop when inorder = [9,3,15,20,7] and postorder = [9,15,7,20,3]?
easy
A. 4
B. 2
C. 1
D. 3
Solution
Step 1: Initialize variables
inorder_index starts at 4 (last index of inorder). The root is 3 (postorder[-1]).
Step 2: First iteration (i=3, node_val=20)
top.val=3 != inorder[4]=7, so attach 20 as right child, stack grows, inorder_index stays 4.
Step 3: Second iteration (i=2, node_val=7)
top.val=20 != inorder[4]=7 is false, so enter else: pop stack while top.val == inorder[inorder_index]. 20 != 7, so no pop, attach 7 as right child, stack grows, inorder_index stays 4.
Step 4: Third iteration (i=1, node_val=15)
top.val=7 == inorder[4]=7, pop 7, inorder_index=3; top.val=20 == inorder[3]=20, pop 20, inorder_index=2; top.val=3 != inorder[2]=15, stop popping. Attach 15 as left child, stack grows.
Final Answer:
Option D -> Option D
Quick Check:
inorder_index decremented twice after popping 7 and 20 [OK]
Hint: inorder_index decrements only when popping matching nodes [OK]
Common Mistakes:
Off-by-one error in inorder_index update
Confusing when to pop stack
Misreading top.val vs inorder[inorder_index]
4. Given a binary tree, you need to find the length of the longest path between any two nodes in the tree. This path may or may not pass through the root. Which approach guarantees an optimal solution to this problem?
easy
A. Perform a postorder traversal computing heights and update the diameter at each node using recursion with a global variable.
B. Apply dynamic programming with memoization on node pairs to find longest paths.
C. Use a greedy traversal that always chooses the deeper subtree at each node.
D. Calculate the height of the tree and multiply by two to estimate the diameter.
Solution
Step 1: Understand the problem requires the longest path between any two nodes, not necessarily passing through root.
The diameter can be found by checking the sum of left and right subtree heights at every node.
Step 2: Recognize that a postorder traversal with recursion and a global variable to track diameter updates at each node ensures all paths are considered.
This approach visits each node once, updating the diameter with left_height + right_height.
Final Answer:
Option A -> Option A
Quick Check:
Postorder traversal with global diameter update covers all nodes [OK]
Hint: Diameter updates at every node, not just root [OK]
Common Mistakes:
Thinking diameter must pass through root
Using greedy to pick deeper subtree only
Confusing diameter with twice height
5. Consider the following Python code implementing the optimal flatten function for a binary tree. Given the input tree:
1
/ \
2 3
What is the value of the global variable prev after the call flatten(root) completes?
easy
A. TreeNode with val=3
B. TreeNode with val=1
C. TreeNode with val=2
D. None
Solution
Step 1: Trace flatten calls on root=1
flatten(1) calls flatten(3) then flatten(2). After flatten(3), prev=TreeNode with val=3; after flatten(2), prev=TreeNode with val=2; finally, root=1 sets root.right=prev (2) and prev=TreeNode with val=1.
Step 2: Final value of prev after flatten(1)
After processing root=1, prev points to the root node with val=1.
Final Answer:
Option B -> Option B
Quick Check:
Global prev ends at root node after full traversal [OK]
Hint: Global prev ends at root after full flatten [OK]
Common Mistakes:
Assuming prev ends at last leaf node
Confusing order of recursive calls
Forgetting prev is updated after rewiring
Recommended
Ready to prove it?
Pass the test and this pattern moves unknownstrongwhile earning +1 Grip toward your certificate.