129. Sum Root to Leaf Numbers 🌟🌟

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.

O(N) Time recursive

We recursively traverse to the all leaf node.
Multiply val by 10 and add curr val in it.
if both left and right child is null, we add the current node value to the sum.
else recurse for left anf right subtree.
Stack can grow upto the height of the tree so that we can explore the path from root to leaf node.
Thus, Space Complexity = O(Height of the tree)
Time Complexity:O(N) –> All Nodes will be visited once.

Code

class Solution{
    int ans = 0;
    void dfs(TreeNode *root, int val){
        if (!root) return;
        val *= 10;
        val += root->val;

        if (root->left == NULL && root->right == NULL){
            ans += val;
            return;
        }
        dfs(root->left, val);
        dfs(root->right, val);
    }

public:
    int sumNumbers(TreeNode *root){
        if (!root) return 0;
        dfs(root, 0);
        return ans;
    }
};

Useful Comment:

List of problems you need to master the concept :

If you find more problems, please comment it below :)