(Note: I think it's a testament nowadays to not copy answers directly from ChatGPT. On that note, I'd like to inform the readers that the below answer has not been derived from ChatGPT nor has it been proofread or even checked grammatically by the software. Everything you'll read here has been typed straight from my mind by my fingers.)

Link To The Question

https://leetcode.com/problems/sum-root-to-leaf-numbers/

Intuition

My first thought was to apply a traversal method. We have many tree traversal methods at our disposal, such as preorder, inorder, postorder, level order etc. Since the root of the tree is supposed to be the MSB for all the numbers that are created on our journey to the various leaves, it would be easy to start processing the root itself first and then move onto the various sub-trees for our root, therefore preorder traversal is suitable here. The processing here will be as follows: if we take the root's value and pass [(number * 10) + root->val] onto the respective subtrees, we create the foundation for the next root to generate the right number while reaching to the leaves.

The nodes are basically saying:- "I have a number passed onto me, I will first process this number, and then I'll pass this number onto my children since I am not a leaf node."

But when does this recursion stop? The edge case is that if the root is NULL, then we return back to the leaf (or if the tree is empty, we return back empty handed). The base case would be that if it's a leaf node, then after processing, we will have our final number with us.

The leaf will say: - "I have a number passed onto me, I will first process this number, and since I don't have any children, this number that I now have is one of the numbers that need to be added to a static/global variable"

One more thing we need to take care of, is that since for each traversal, we pass our processed number onto the children, we would also need to start our traversal from the root of the tree with the number 0 passed onto it.

Approach

1. Create a global variable "sum" which is initialized to 0.

2. we have two functions, the main function which is called by the website, and the "preorder" function which is called within the main function. Once this "preroder" function is done executing, the global sum variable will be updated with the answer.

3. In the preorder traversal, we pass in the root of the tree, and 0. This is because each node of the tree will recieve a number from its parent node. This number will be processed further. (processing :- number*10 + node->val)

4. Each node first processes the number given to it, and then decides that either it passes onto its children (i.e if the node has any children), or if the number generated is the final number generated on this journey (i.e. if the node is a leaf node).

5. if the node is a leaf node, the number generated currently will be added to the global sum variable, else the recursive traversal will continue through the children of the current node.

Complexity

• Time complexity:

Since each node of the tree is processed once, and for each node, processing takes O(1) time, we can say that the time complexity is O(n)

• Space complexity:

Space complexity here will be in terms of the maximum length of the function call stack. since this is a tree traversal function, the call stack would have at max "height of the tree" calls. therefore O(h). In the worst case, if we have a skewed tree, the height of the tree will be equal to the number of nodes, therefore O(n)

Code

    int sum = 0;
    void preorder(TreeNode *root, int s)
        {
        if (root==NULL) return;
        int ns = s*10 + root->val;
        if (root->left) preorder(root->left,ns);
        if (root->right) preorder(root->right,ns);
        if (root->left==NULL && root->right==NULL) sum+=ns;
        } 

    int sumNumbers(TreeNode* root) 
        {
        preorder(root, 0);
        return sum;
        }