Sum Root To Leaf Numbers

                                            
/**
 * 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) {}
 */

class Solution {
public:
    int sumNumbers(TreeNode* root) {
        return dfs(root, 0);
    }
    
    int dfs(TreeNode* node, int currSum) {
        if (node == nullptr) {
            return 0;
        }
        
        currSum = currSum * 10 + node->val;
        
        if (node->left == nullptr && node->right == nullptr) {
            return currSum;
        }
        
        int leftSum = dfs(node->left, currSum);
        int rightSum = dfs(node->right, currSum);
        
        return leftSum + rightSum;
    }
};

                                            
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public int sumNumbers(TreeNode root) {
        return dfs(root, 0);
    }
    
    private int dfs(TreeNode node, int currentSum) {
        if (node == null) {
            return 0;
        }
        
        int newSum = currentSum * 10 + node.val;
        
        if (node.left == null && node.right == null) {
            return newSum;
        }
        
        return dfs(node.left, newSum) + dfs(node.right, newSum);
    }
}

                                            
# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution(object):
    def sumNumbers(self, root):
        def dfs(node, current_sum):
            if not node:
                return 0
            current_sum = current_sum * 10 + node.val
            if not node.left and not node.right:
                return current_sum
            return dfs(node.left, current_sum) + dfs(node.right, current_sum)
        
        return dfs(root, 0)

                                            
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
int sumNumbers(struct TreeNode* root) {
    if (root == NULL) return 0;
    
    int sum = 0;
    helper(root, 0, &sum);
    
    return sum;
}

void helper(struct TreeNode* node, int pathSum, int* total) {
    if (node == NULL) return;
    
    pathSum = pathSum * 10 + node->val;
    
    if (node->left == NULL && node->right == NULL) {
        *total += pathSum;
        return;
    }
    
    helper(node->left, pathSum, total);
    helper(node->right, pathSum, total);
}

                                            
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left;
 *     public TreeNode right;
 *     public TreeNode(int val=0, TreeNode left=null, TreeNode right=null) {
 */
public class Solution {
    public int SumNumbers(TreeNode root) {
        return DFS(root, 0);
    }
    
    private int DFS(TreeNode node, int currentSum) {
        if (node == null) return 0;
        
        currentSum = currentSum * 10 + node.val;
        
        if (node.left == null && node.right == null) {
            return currentSum;
        }
        
        int leftSum = DFS(node.left, currentSum);
        int rightSum = DFS(node.right, currentSum);
        
        return leftSum + rightSum;
    }
}

                                            
/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */

var sumNumbers = function(root) {
    let sum = 0;
    const dfs = (node, value) => {
        if (!node) return;
        
        value = value * 10 + node.val;
        
        if (!node.left && !node.right) {
            sum += value;
            return;
        }
        
        dfs(node.left, value);
        dfs(node.right, value);
    };
    
    dfs(root, 0);
    
    return sum;
};

                                            
/**
 * Definition for a binary tree node.
 * class TreeNode {
 *     val: number
 *     left: TreeNode | null
 *     right: TreeNode | null
 *     constructor(val?: number, left?: TreeNode | null, right?: 
TreeNode | null) {
 */

function sumNumbers(root: TreeNode | null): number {
    if (!root) {
        return 0;
    }
    
    let totalSum = 0;
    
    const dfs = (node: TreeNode, currentSum: number) => {
        currentSum = currentSum * 10 + node.val;
        
        if (!node.left && !node.right) {
            totalSum += currentSum;
            return;
        }
        
        if (node.left) {
            dfs(node.left, currentSum);
        }
        
        if (node.right) {
            dfs(node.right, currentSum);
        }
    };
    
    dfs(root, 0);
    
    return totalSum;
}

                                            
/**
 * Definition for a binary tree node.
 * class TreeNode {
 *     public $val = null;
 *     public $left = null;
 *     public $right = null;
 *     function __construct($val = 0, $left = null, $right = null) {
 *         $this->val = $val;
 */

class Solution {
    /**
     * @param TreeNode $root
     * @return Integer
     */
    function sumNumbers($root, $prevSum = 0) {
        if ($root == null) {
            return 0;
        }
        
        $currentSum = $prevSum * 10 + $root->val;
        
        if ($root->left == null && $root->right == null) {
            return $currentSum;
        }
        
        return $this->sumNumbers($root->left, $currentSum) + $this->sumNumbers($root->right, $currentSum);  
    }
}

                                            
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     public var val: Int
 *     public var left: TreeNode?
 *     public var right: TreeNode?
 *     public init() { self.val = 0; self.left = nil; self.right = nil; }
 *     public init(_ val: Int) { self.val = val; self.left = nil; self.right = nil; }
 *     public init(_ val: Int, _ left: TreeNode?, _ right: TreeNode?) {
 *         self.val = val
 *         self.left = left
 *         self.right = right
 *     }
 * }
 */

class Solution {
    func sumNumbers(_ root: TreeNode?) -> Int {
        return dfs(root, 0)
    }
    
    func dfs(_ node: TreeNode?, _ currentSum: Int) -> Int {
        guard let node = node else { return 0 }
        
        let newSum = currentSum * 10 + node.val
        
        if node.left == nil, node.right == nil {
            return newSum
        }
        
        return dfs(node.left, newSum) + dfs(node.right, newSum)
    }
}

                                            
/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
 
func sumNumbers(root *TreeNode) int {
    return dfs(root, 0)
}

func dfs(node *TreeNode, num int) int {
    if node == nil {
        return 0
    }
    
    num = num*10 + node.Val
    
    if node.Left == nil && node.Right == nil {
        return num
    }
    
    return dfs(node.Left, num) + dfs(node.Right, num)
}

                                            
# Definition for a binary tree node.
# class TreeNode
#     attr_accessor :val, :left, :right
#     def initialize(val = 0, left = nil, right = nil)
#         @val = val
#         @left = left
#         @right = right
#     end

def sum_numbers(root, sum = 0)
    return 0 if root.nil?
    
    sum = sum * 10 + root.val
    
    return sum if root.left.nil? && root.right.nil?
    
    return sum_numbers(root.left, sum) + sum_numbers(root.right, sum)
end

                                            
object Solution {
    def sumNumbers(root: TreeNode): Int = {
        def dfs(node: TreeNode, current: Int): Int = {
            if (node == null) return 0
            val next = current * 10 + node.value
            if (node.left == null && node.right == null) return next
            dfs(node.left, next) + dfs(node.right, next)
        }
        
        dfs(root, 0)
    }
}

                                            
%% Definition for a binary tree node.
%%
%% -record(tree_node, {val = 0 :: integer(),
%%                     left = null  :: 'null' | #tree_node{},
%%                     right = null :: 'null' | #tree_node{}}).
-spec sum_numbers(Root :: #tree_node{} | null) -> integer().
sum_numbers(Root) ->
    sum_numbers(Root, 0).
    
sum_numbers(null, Sum) ->
    Sum;
sum_numbers(#tree_node{val = Val, left = null, right = null}, Sum) ->
    Sum * 10 + Val;
sum_numbers(#tree_node{val = Val, left = Left, right = null} = Root, Sum) ->
    sum_numbers(Left, Sum * 10 + Val);
sum_numbers(#tree_node{val = Val, left = null, right = Right} = Root, Sum) ->
    sum_numbers(Right, Sum * 10 + Val);
sum_numbers(#tree_node{val = Val, left = Left, right = Right} = Root, Sum) ->
    sum_numbers(Left, Sum * 10 + Val) + sum_numbers(Right, Sum * 10 + Val).

To solve this coding challenge, you need to traverse a binary tree and calculate the sum of all numbers formed by the paths from the root to the leaf nodes. Each path will represent a number which is formed by concatenating the values of the nodes from the root to the leaf. The sum of all these numbers is the solution.

# Explanation

The goal is to sum up all the numbers formed by the paths from the root to leaf nodes. We can achieve this by using a Depth-First Search (DFS) approach, which explores each root-to-leaf path one by one.

Initialization and Class Definition:

First, initialize the basic structure of the node (TreeNode) which contains the value, a pointer to the left child, and a pointer to the right child.
Define the main solution class that contains the method
sumNumbers

.

Helper Function (DFS):

Create a helper function
dfs

to traverse the tree.
This function takes two parameters: the current node and the current sum formed by the path.
The current sum needs to be updated as we traverse down the tree.

Base Case:

If the current node is
None

, return 0 because there is no number formed.

Leaf Node Check:

If the current node is a leaf (both left and right children are
None

), then the sum formed up to this node is a complete number. Return this sum.

Recursive Case:

Recursively call the
dfs

function for the left and right children while passing the updated sum.
Sum the results from the left and right recursive calls.

Returning the Final Sum:

Initialize the DFS with the root node and the initial sum as 0 and return the result.

### Step-by-Step Explanation / Detailed Steps in Pseudocode ###

Define node structure:

Each node in the tree will have a value (
val

), a left child (
left

), and a right child (
right

).

Define the main solution class:

Inside this class, define a method
sumNumbers

.

Define the helper DFS function:

This function will take a node and the current value formed from the root to that node.
If the node is
None

, return 0 (base case).
Update the current value by multiplying it by 10 and adding the node's value.
If the node is a leaf (both children are
None

), return the current value (leaf node case).
Sum the results from the left and right children.

Call the DFS function from the root:

Initialize the DFS by calling it with the root node and 0.
Return the result of the DFS call.

### Pseudocode with Comments ###

                                            
// Define a node structure to represent each node in the binary tree
class TreeNode:
    function __init__(val=0, left=null, right=null):
        self.val = val   // value of the node
        self.left = left // left child
        self.right = right // right child

                                            
// Define the main solution class containing the method to calculate sum
class Solution:
    function sumNumbers(root):
        // Define the helper function for DFS traversal
        function dfs(node, current_sum):
            if node is null:
                return 0 // base case: if the node is null, no number is formed

            // Update the current sum to include this node's value
            current_sum = current_sum * 10 + node.val

            // Check if the node is a leaf node (no children)
            if node.left is null and node.right is null:
                return current_sum // return the complete number for this path

            // Recursively calculate the sum for the left and right children
            left_sum = dfs(node.left, current_sum)
            right_sum = dfs(node.right, current_sum)

            // Return the total sum from both subtrees
            return left_sum + right_sum
        
        // Initialize the DFS with the root node and initial sum of 0
        return dfs(root, 0)

In this pseudocode:

TreeNode class serves as the blueprint for constructing each node in the binary tree.
Solution class contains the
sumNumbers

method, which in turn uses a helper method
dfs

to perform the DFS traversal and calculate the sum of all root-to-leaf numbers.
The
dfs

function is responsible for traversing the tree, updating current path sums, and checking for leaf nodes to aggregate the results.