DEV Community

Cover image for 129. Sum Root to Leaf Numbers
MD ARIFUL HAQUE
MD ARIFUL HAQUE

Posted on • Edited on

129. Sum Root to Leaf Numbers

129. Sum Root to Leaf Numbers

Difficulty: Medium

Topics: Tree, Depth-First Search, Binary Tree

You are given the root of a binary tree containing digits from 0 to 9 only.

Each root-to-leaf path in the tree represents a number.

  • For example, the root-to-leaf path 1 -> 2 -> 3 represents the number 123.

Return the total sum of all root-to-leaf numbers. Test cases are generated so that the answer will fit in a 32-bit integer.

A leaf node is a node with no children.

Example 1:

  • Input: root = [1,2,3]
  • Output: 25
  • Explanation:
    • The root-to-leaf path 1->2 represents the number 12.
    • The root-to-leaf path 1->3 represents the number 13.
    • Therefore, sum = 12 + 13 = 25.

Example 2:

  • Input: root = [4,9,0,5,1]
  • Output: 1026
  • Explanation:
    • The root-to-leaf path 4->9->5 represents the number 495.
    • The root-to-leaf path 4->9->1 represents the number 491.
    • The root-to-leaf path 4->0 represents the number 40.
    • Therefore, sum = 495 + 491 + 40 = 1026.

Constraints:

  • The number of nodes in the tree is in the range [1, 1000].
  • 0 <= Node.val <= 9
  • The depth of the tree will not exceed 10.

Solution:

We can use a Depth-First Search (DFS) approach. The idea is to traverse the tree, keeping track of the number formed by the path from the root to the current node. When you reach a leaf node, you add the current number to the total sum.

Let's implement this solution in PHP: 129. Sum Root to Leaf Numbers

Explanation:

  1. TreeNode Class: This class represents each node of the binary tree. Each node has a value (val), a left child (left), and a right child (right).

  2. sumNumbers Function: This is the main function that initiates the DFS traversal by calling the sumNumbersRecu function with the root node and an initial currentSum of 0.

  3. sumNumbersRecu Function:

    • Base Case: If the node is null, return 0 (this handles the case where there is no child node).
    • Update Current Sum: For each node, update the currentSum by multiplying the previous currentSum by 10 and adding the node's value.
    • Leaf Node Check: If the node is a leaf (i.e., it has no left or right child), return the currentSum as this represents the number formed by the path from the root to this leaf.
    • Recursive Calls: If the node is not a leaf, recursively call sumNumbersRecu on both the left and right children and return their sum.

Edge Cases:

  • The function handles cases where the tree has only one node.
  • It correctly computes the sum even for deeper trees, as the depth of the tree will not exceed 10 (as per the problem constraints).

This solution runs efficiently with a time complexity of O(n), where n is the number of nodes in the tree. This is because each node is visited exactly once. The space complexity is O(h), where h is the height of the tree, due to the recursion stack.

Contact Links

If you found this series helpful, please consider giving the repository a star on GitHub or sharing the post on your favorite social networks 😍. Your support would mean a lot to me!

If you want more helpful content like this, feel free to follow me:

Image of Timescale

Timescale – the developer's data platform for modern apps, built on PostgreSQL

Timescale Cloud is PostgreSQL optimized for speed, scale, and performance. Over 3 million IoT, AI, crypto, and dev tool apps are powered by Timescale. Try it free today! No credit card required.

Try free

Top comments (0)

AWS Security LIVE!

Tune in for AWS Security LIVE!

Join AWS Security LIVE! for expert insights and actionable tips to protect your organization and keep security teams prepared.

Learn More

👋 Kindness is contagious

Immerse yourself in a wealth of knowledge with this piece, supported by the inclusive DEV Community—every developer, no matter where they are in their journey, is invited to contribute to our collective wisdom.

A simple “thank you” goes a long way—express your gratitude below in the comments!

Gathering insights enriches our journey on DEV and fortifies our community ties. Did you find this article valuable? Taking a moment to thank the author can have a significant impact.

Okay