Sum Root to Leaf Numbers

Medium · Graphs · Explanation and code example

Morris Traversal

How it works

Morris traversal allows us to traverse the tree without using extra space for a stack or recursion. It temporarily modifies the tree by creating links from predecessors back to their successors. The challenge here is tracking the accumulated number: when we return to a node via a temporary link, we need to "undo" the digits we added while going down the left subtree. We track the number of steps taken to reach the predecessor and divide by the corresponding power of 10 to remove those digits.

Steps

  1. Precompute powers of 10 for quick division.
  2. While the current node exists:
    • If no left child exists:
      • Add the current digit to the number.
      • If no right child exists (leaf), add number to result.
      • Move to the right child.
    • Otherwise, find the inorder predecessor (rightmost node in left subtree) while counting steps:
      • If predecessor's right is null, create a temporary link to current, add digit to number, and move left.
      • If predecessor's right points to current (revisiting), remove the link. If predecessor is a leaf, add number to result. Divide number by 10^steps to remove the left subtree digits. Move right.
  3. Return the result.

Complexity

  • Time complexity: O(n)
  • Space complexity: O(1) extra space.

Things to watch for

Adding Non-Leaf Node Values to the Sum

A frequent mistake is adding the accumulated number to the result at every node instead of only at leaf nodes. The problem specifically asks for root-to-leaf path numbers, so you must check that both left and right children are null before adding to the sum. Adding at internal nodes will count partial paths and produce incorrect results.

Incorrect Number Accumulation Formula

When building the number along a path, you must multiply the current accumulated value by 10 before adding the new digit: num = num * 10 + node.val. A common error is adding the digit first or forgetting to multiply, which produces single-digit values or incorrect concatenation. Remember that each level represents a new decimal place.

Not Handling Single-Node Trees

When the tree has only a root node with no children, that single node is itself a leaf. Some implementations incorrectly return 0 for this case or fail to recognize it as a valid path. Ensure your base case properly handles when the root exists but has no children, returning just the root's value as the complete number.

Python code example

from typing import Optional

# Definition for a binary tree node.
# 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: Optional[TreeNode]) -> int:
        res = 0
        cur = root
        num = 0
        power = [1] * 10
        for i in range(1, 10):
            power[i] *= power[i - 1] * 10

        while cur:
            if not cur.left:
                num = num * 10 + cur.val
                if not cur.right:
                    res += num
                cur = cur.right
            else:
                prev = cur.left
                steps = 1
                while prev.right and prev.right != cur:
                    prev = prev.right
                    steps += 1

                if not prev.right:
                    prev.right = cur
                    num = num * 10 + cur.val
                    cur = cur.left
                else:
                    prev.right = None
                    if not prev.left:
                        res += num
                    num //= power[steps]
                    cur = cur.right

        return res

C++ code example

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    int sumNumbers(TreeNode* root) {
        int res = 0, num = 0;
        int power[10] = {1};
        for (int i = 1; i < 10; i++) {
            power[i] = power[i - 1] * 10;
        }

        TreeNode* cur = root;
        while (cur) {
            if (!cur->left) {
                num = num * 10 + cur->val;
                if (!cur->right) res += num;
                cur = cur->right;
            } else {
                TreeNode* prev = cur->left;
                int steps = 1;
                while (prev->right && prev->right != cur) {
                    prev = prev->right;
                    steps++;
                }

                if (!prev->right) {
                    prev->right = cur;
                    num = num * 10 + cur->val;
                    cur = cur->left;
                } else {
                    prev->right = nullptr;
                    if (!prev->left) res += num;
                    num /= power[steps];
                    cur = cur->right;
                }
            }
        }
        return res;
    }
};
Source and license

Adapted from NeetCode’s source · MIT license. Node types are supplied by LeetCode where needed.

Check the explanation on LeetCode Watch NeetCode on YouTube

Your recall check is in progress. Write your attempt before revealing the explanation.

Resume recall check

Browse all problem explanations