class Solution {
public:
    int result = 0;
    void traverse(TreeNode* root, int sum) {
        if(root == nullptr) return;

        int newSum = sum + root->val;
        if(root->left == nullptr && root->right == nullptr) {
            // leaf, add sum to result
            result += newSum;
            return;
        }
        
        newSum *= 10;
        if(root->left != nullptr) traverse(root->left, newSum);
        if(root->right != nullptr) traverse(root->right, newSum);
    }

    int sumNumbers(TreeNode* root) {
        traverse(root, 0);
        return result;
    }
};

class Solution {
public:
    int sumNumbers(TreeNode* root) {
        if(root == nullptr) return 0;

        int result = 0;
        int currentSum = 0;

        stack<pair<TreeNode*,int>> sta;

        sta.push({root, 0});

        while(!sta.empty()) {
            pair<TreeNode*,int> node = sta.top();
            sta.pop();
            
            currentSum = node.second * 10 + node.first->val;

            if(node.first->left == nullptr && node.first->right == nullptr) {
                result += currentSum;
            }

            if(node.first->right != nullptr) sta.push({node.first->right, currentSum});
            if(node.first->left != nullptr) sta.push({node.first->left, currentSum});
            
        }

        return result;
    }
};