Bird
Raised Fist0
Interview Preptree-dfsmediumAmazonGoogleFacebook

Sum Root to Leaf Numbers

Choose your preparation mode4 modes available
▶
Steps
setup

Initialize variables and start at root

Set total sum to 0, current_number to 0, and start traversal at the root node with value 1.

💡 Initialization sets up the variables needed to track the sum and the current path number as we traverse.
Line:total = 0 current_number = 0 node = root
💡 We begin traversal at the root with no accumulated number or sum.
📊
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

  1. Step 1: Understand traversal order requirement

    Inorder traversal visits left subtree, then node, then right subtree, matching the problem's order.
  2. 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.
  3. Final Answer:

    Option C -> Option C
  4. 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

  1. 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.
  2. 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.
  3. Final Answer:

    Option A -> Option A
  4. 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

  1. Step 1: Initialize variables

    inorder_index starts at 4 (last index of inorder). The root is 3 (postorder[-1]).
  2. 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.
  3. 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.
  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.
  5. Final Answer:

    Option D -> Option D
  6. 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

  1. 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.
  2. 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.
  3. Final Answer:

    Option A -> Option A
  4. 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

  1. 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.
  2. Step 2: Final value of prev after flatten(1)

    After processing root=1, prev points to the root node with val=1.
  3. Final Answer:

    Option B -> Option B
  4. 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 unknown strong while earning +1 Grip toward your certificate.

10 questions~5 mineasy hard