Skip to content
TheChatArchiveThe Chat Archive
Step 3.5 Flash· unknownHugging Face Frontier Reasoning Traces

You are given a binary tree. Write a function to find the "sum of all leaf nodes".…

  1. User

    You are given a binary tree. Write a function to find the "sum of all leaf nodes". Please write a function that solves this problem, and explain your algorithm.

  2. Assistant

    We are given a binary tree. We need to find the sum of all leaf nodes. A leaf node is a node that has no children (i.e., both left and right are null).

    Steps:

    1. We traverse the tree (using any traversal: pre-order, in-order, post-order).
    2. For each node, check if it is a leaf (left and right are null). If it is, add its value to the sum.
    3. Return the sum.

    We can do this recursively or iteratively. Let's do a recursive approach for simplicity.

    Let's define a function sum_of_leaves(root) that returns the sum of leaf nodes in the tree rooted at root.

    Base case: if root is None, return 0. Otherwise: if root is a leaf (root.left is None and root.right is None), then return root.val. else, return the sum of leaves in the left subtree plus the sum of leaves in the right subtree.

    Alternatively, we can do an iterative traversal (like DFS or BFS) and accumulate the sum when we encounter a leaf.

    Let's write the recursive version.

    Example: Tree: 1 /
    2 3 /
    4 5

    Leaves are 4,5,3. Sum = 4+5+3 = 12.

    However, note: the problem says "binary tree", so it's not necessarily a BST.

    Let's code accordingly.

    We assume the tree node structure as: class TreeNode: def init(self, val=0, left=None, right=None): self.val = val self.left = left self.right = right

    But note: the problem does not specify the language. Let's write in Python.

    We are to write a function that takes the root of the binary tree and returns an integer.

    Let's define:

    def sum_of_leaves(root: TreeNode) -> int:

    Implementation:

    if root is None: return 0 if root.left is None and root.right is None: return root.val else: return sum_of_leaves(root.left) + sum_of_leaves(root.right)

    However, note: what if the tree has only one node? Then that node is a leaf and we return its value.

    But wait: what if the tree is empty? Then we return 0.

    Let's test with the example:

    root = TreeNode(1) root.left = TreeNode(2) root.right = TreeNode(3) root.left.left = TreeNode(4) root.left.right = TreeNode(5)

    sum_of_leaves(root) -> root is not leaf -> sum_of_leaves(2) + sum_of_leaves(3) For 2: not leaf (has left and right) -> sum_of_leaves(4) + sum_of_leaves(5) For 4: leaf -> 4 For 5: leaf -> 5 So for 2: 4+5=9 For 3: leaf -> 3 Total: 9+3=12.

    This matches.

    However, note: the problem says "sum of all leaf nodes". This recursive approach is straightforward.

    But what about an iterative approach? We can do a DFS (using a stack) or BFS (using a queue). Let's also consider that.

    Iterative DFS:

    stack = [root] total = 0 while stack: node = stack.pop() if node is not None: if node.left is None and node.right is None: total += node.val else: if node.right: stack.append(node.right) if node.left: stack.append(node.left)

    return total

    This will also work.

    Since the problem does not specify, I'll write both for completeness? But the instruction says "write a function", so I'll choose one.

    Let's write the recursive one because it's concise.

    However, note: the recursive approach may lead to stack overflow for very deep trees. But for the purpose of this problem, it's acceptable.

    But the problem says "You are given a binary tree." It doesn't specify the size, so we assume it's manageable.

    Let's write the recursive function.

    But wait, what if the tree has negative values? The problem doesn't specify, so we assume integers (positive and negative) and we just sum.

    We'll write:

    def sum_of_leaves(root): if not root: return 0 if not root.left and not root.right: return root.val return sum_of_leaves(root.left) + sum_of_leaves(root.right)

    However, note: the above recursive function will not work if the tree has only one node? Actually, it will because the root is a leaf.

    But what if the tree is empty? We return 0.

    Let's test with a tree of one node (val=5): root = TreeNode(5) sum_of_leaves(root) -> 5.

    So it's correct.

    But note: the problem says "leaf nodes", and in a tree with one node, that node is a leaf.

    However, there is a nuance: in some definitions, the root of a tree with one node is considered a leaf. So we are good.

    Now, let's write the code accordingly.

    But note: the problem does not specify the tree node class. We assume it's defined as above.

    If we are to write a complete solution, we should include the TreeNode class? The problem says "You are given a binary tree", so we assume the tree node is already defined.

    However, in the function, we are only given the root. So we don't need to define TreeNode if it's already defined.

    But in the code we submit, if we are to run it, we might need to define it. Since the problem says "write a function", I think we just write the function.

    However, in the explanation, we can note the assumption.

    Let's write:

    Definition for a binary tree node.

    class TreeNode:

    def init(self, val=0, left=None, right=None):

    self.val = val

    self.left = left

    self.right = right

    class Solution: def sumOfLeaves(self, root: Optional[TreeNode]) -> int: if not root: return 0 if not root.left and not root.right: return root.val return self.sumOfLeaves(root.left) + self.sumOfLeaves(root.right)

    But note: the function name in the problem is not specified. Let's call it sum_of_leaves as in the problem statement.

    However, the problem says "Write a function", so I'll write a standalone function.

    But in many online judges, they expect a method in a class. Since the problem says "write a function", I'll write a function that takes the root.

    Let me write:

    def sum_of_leaves(root): # recursive

    But note: if we are in an OOP context, we might have to define a class. Since the problem does not specify, I'll write a function.

    However, to be safe for LeetCode-style, I'll write:

    class Solution: def sumOfLeaves(self, root: TreeNode) -> int: ...

    But the problem says "write a function", so I think a function is acceptable.

    Let me write the function as:

    def sum_of_leaves(root): if root is None: return 0 if root.left is None and root.right is None: return root.val return sum_of_leaves(root.left) + sum_of_leaves(root.right)

    But wait: what if the tree has a node with one child? Then that node is not a leaf, so we don't add it. We only add when both children are None.

    This is correct.

    However, note: the above recursive function may be inefficient for very deep trees because of recursion depth.

    We can also write an iterative version to avoid recursion depth issues.

    Let me write an iterative version using a stack (DFS):

    def sum_of_leaves_iterative(root): if not root: return 0 stack = [root] total = 0 while stack: node = stack.pop() if node.left is None and node.right is None: total += node.val if node.right: stack.append(node.right) if node.left: stack.append(node.left) return total

    This is also correct.

    Which one to choose? Since the problem does not specify constraints, I'll choose the recursive for simplicity.

    But note: the problem says "binary tree", so it's not necessarily balanced. The recursive version may hit recursion limit for very deep trees.

    However, in practice, for an interview, the recursive version is acceptable and easier to write.

    Let me write the recursive version.

    But wait: the problem says "explain your algorithm". So I'll explain both? Or just one?

    Since the problem says "write a function", I'll write one function. I'll write the recursive one.

    However, to be thorough, I'll mention that an iterative version exists and is better for very deep trees.

    But in the code, I'll write the recursive one.

    Let's write:

    def sum_of_leaves(root): if root is None: return 0 if root.left is None and root.right is None: return root.val return sum_of_leaves(root.left) + sum_of_leaves(root.right)

    But note: the function name in the problem is "sum of all leaf nodes", so I'll name it sum_of_leaves.

    However, in the example, they might expect a method. But the problem says "function".

    I think it's safe.

    Let me write the code accordingly.

    But wait: what if the tree has a node with one child? Then we don't count that node. That's correct.

    Example: 1 / 2

    Leaves: only 2? But wait, 2 has no children? It has no children? Actually, 2 has no children? In this tree, 2 has no children, so it's a leaf.

    But what about: 1 /
    2 3
    4

    Leaves: 4 and 3? Yes.

    Our function: 1 -> not leaf -> sum(2) + sum(3) 2 -> not leaf (has right) -> sum(None) + sum(4) = 0 + 4 = 4 3 -> leaf -> 3 4 -> leaf -> 4 (wait, we already counted 4 in the call for 2? No, because when we call sum(2), we get 4. Then when we call sum(3) we get 3. Then total 7.

    But wait, the leaves are 4 and 3? Actually, 4 is a leaf and 3 is a leaf. So 4+3=7. Correct.

    However, in the tree, 2 is not a leaf because it has a right child.

    So our function is correct.

    Let's code accordingly.

    But note: the function above for node 2: node 2: has left? None, has right? 4 -> not leaf -> then we call sum_of_leaves(None) and sum_of_leaves(4). sum_of_leaves(None) returns 0, sum_of_leaves(4) returns 4 because 4 has no children.

    So it works.

    Now, let's write the code.

    However, note: the problem says "binary tree", so we don't assume any order.

    We are just summing all nodes that have no children.

    This is the same as the definition of leaf.

    So we are done.

    But wait: what if the tree has negative values? We are just adding, so it's fine.

    Let's code.

    However, note: the problem does not specify the data type of the node values. We assume they are numbers.

    So the function:

    def sum_of_leaves(root): if not root: return 0 if not root.left and not root.right: return root.val return sum_of_leaves(root.left) + sum_of_leaves(root.right)

    This is the recursive version.

    Alternatively, we can write:

    def sum_of_leaves(root): if not root: return 0 total = 0 if not root.left and not root.right: total += root.val total += sum_of_leaves(root.left) total += sum_of_leaves(root.right) return total

    But that does extra work because we are calling on both children even if the current node is a leaf? Actually, if the current node is a leaf, then its children are None, so the recursive calls return 0. But it's less efficient.

    So the first version is better.

    Let me stick to the first.

    Now, for the iterative version:

    def sum_of_leaves_iterative(root): if not root: return 0 stack = [root] total = 0 while stack: node = stack.pop() if node.left is None and node.right is None: total += node.val if node.right: stack.append(node.right) if node.left: stack.append(node.left) return total

    This is DFS (pre-order). We can also do BFS.

    But again, the problem doesn't specify.

    Since the problem says "write a function", I'll write the recursive one because it's shorter.

    However, note: the iterative version uses a stack and may be more efficient in terms of recursion limit.

    But for the purpose of this problem, I think recursive is acceptable.

    Let me write the recursive function.

    But wait: what if the tree is very large? The recursive version may cause stack overflow.

    So perhaps we should write iterative to be safe.

    Since the problem does not specify the constraints, I'll write both and let the user choose? But the problem says "write a function", so one function.

    I think in an interview, they might ask for both. But here, we are to write one.

    I'll write the iterative one to avoid recursion depth issues.

    But the iterative one is also simple.

    Let me write the iterative one.

    Steps for iterative:

        if root is None: return 0
        initialize a stack with root
        total = 0
        while stack is not empty:
            pop a node
            if node is leaf: add to total
            push right child if exists
            push left child if exists
    
        return total
    

    This is pre-order DFS.

    Alternatively, we can do:

        stack = [root]
        total = 0
        while stack:
            node = stack.pop()
            if node:
                if not node.left and not node.right:
                    total += node.val
                stack.append(node.right)
                stack.append(node.left)
    

    But note: we are pushing even if node is None? In the above, we check if node is not None at the beginning of the loop? Actually, we are popping and then checking if node is not None? Wait, in the code above, we are not checking for None when popping. We are pushing None? We should not push None.

    In the iterative version I wrote earlier, we only push if the child exists.

    So:

        if node.right: stack.append(node.right)
        if node.left: stack.append(node.left)
    

    This way we don't push None.

    But if we do:

        stack.append(node.right)
        stack.append(node.left)
    

    without checking, then we will have None in the stack. Then when we pop, we get None and then we try to check node.left and node.right? That would cause an error.

    So we must check before pushing.

    Alternatively, we can check when popping:

        node = stack.pop()
        if node is None:
            continue
        ... then check for leaf and then push children (without checking for None? Then we push None and then skip when we pop? That would work too but less efficient.
    

    So the version that checks before pushing is better.

    Let me write:

        def sum_of_leaves(root):
            if not root:
                return 0
            stack = [root]
            total = 0
            while stack:
                node = stack.pop()
                if node.left is None and node.right is None:
                    total += node.val
                if node.right:
                    stack.append(node.right)
                if node.left:
                    stack.append(node.left)
            return total
    

    This is safe.

    Now, which one to choose? I think the iterative one is more robust for large trees.

    But the problem does not specify the size, so I'll go with iterative.

    However, the recursive one is more straightforward and easier to understand.

    Since the problem says "explain your algorithm", I'll explain the recursive one because it's simpler to explain.

    But then I'll write the iterative one? Or the recursive?

    Let me decide: I'll write the recursive one because it's shorter and the problem doesn't specify the tree size.

    But to be safe, I'll write the iterative one.

    Actually, I think both are acceptable.

    Since the problem says "write a function", I'll write the recursive one and then mention that an iterative version can be used to avoid recursion depth.

    But the instruction says "write a function that solves this problem", so I must write one.

    I'll write the recursive one and then in the explanation, I'll mention the iterative alternative.

    Let me write:

    Algorithm (recursive): 1. If the current node is None, return 0. 2. If the current node is a leaf (both left and right are None), return its value. 3. Otherwise, return the sum of the leaves in the left subtree and the sum of the leaves in the right subtree.

    This is a simple depth-first traversal.

    Time complexity: O(n) where n is the number of nodes in the tree, because we visit each node exactly once. Space complexity: O(h) where h is the height of the tree, because of the recursion stack.

    For the iterative version, space complexity is O(h) as well (in the worst case, the stack can hold up to h nodes, but in a balanced tree it's O(log n), in a skewed tree it's O(n)).

    Now, let's write the code.

    But note: the problem says "binary tree", so it's not necessarily balanced. So the worst-case height is O(n).

    So both have O(n) worst-case space.

    I'll write the recursive.

    However, if the tree is very deep (like 10,000 nodes in a chain), then recursion might hit the recursion limit in Python.

    So maybe iterative is better.

    But for the purpose of this problem, I think recursive is acceptable.

    Let me write the recursive.

    But wait: the problem says "You are given a binary tree." and we are writing a function. In an interview, they might ask for iterative if the tree is large.

    Since we don't know, I'll write the iterative one.

    Let me write the iterative version.

    Code:

    def sum_of_leaves(root): if not root: return 0 stack = [root] total = 0 while stack: node = stack.pop() # Check if leaf if node.left is None and node.right is None: total += node.val # Push children in reverse order? We are doing pre-order, but the order doesn't matter for sum. # We push right then left so that left is processed first? Actually, in the stack, we push right then left, so left is popped first. # But for sum, order doesn't matter. if node.right: stack.append(node.right) if node.left: stack.append(node.left) return total

    This is correct.

    Let me test with the example:

        Tree:
            1
           / \
          2   3
         / \
        4   5
    
        Stack: [1] -> pop 1 (not leaf) -> push 3, then push 2 -> stack=[3,2]
        Pop 2 -> not leaf -> push 5, then push 4 -> stack=[3,5,4]
        Pop 4 -> leaf -> total=4 -> stack=[3,5]
        Pop 5 -> leaf -> total=9 -> stack=[3]
        Pop 3 -> leaf -> total=12 -> stack empty.
    

    Correct.

    Now, let's write the function.

    Since the problem says "write a function", I'll write:

    def sum_of_leaves(root): ...

    But note: the root can be None.

    We have handled that.

    So I'll write the iterative version.

    However, the problem does not specify the tree node structure. We assume:

        class TreeNode:
            def __init__(self, val=0, left=None, right=None):
                self.val = val
                self.left = left
                self.right = right
    

    But we don't need to define it if it's already given.

    So in the function, we assume root is of type TreeNode or None.

    Let's write the code accordingly.

    I think we are done.

    But wait: what about the case when the tree has only one node? Then:

        stack = [root] -> pop root, it is leaf (because left and right are None) -> total = root.val -> then no children pushed -> return root.val.
    

    Correct.

    So the function works.

    Now, let's write the function and the explanation.

    Explanation:

    We use an iterative depth-first search (DFS) approach. We start by pushing the root node onto a stack. Then, while the stack is not empty, we pop a node. If the node is a leaf (both left and right children are None), we add its value to the total. Then, we push the right child first and then the left child onto the stack (so that the left subtree is processed first in the next iteration). This ensures we visit every node exactly once. The order of traversal does not matter for the sum.

    Time Complexity: O(n) where n is the number of nodes in the tree, because we visit each node once. Space Complexity: O(h) where h is the height of the tree. In the worst case (a skewed tree), the stack can hold up to n nodes, but in a balanced tree, it's O(log n).

    Alternatively, we can use a queue for BFS, but the space complexity would be the same (the maximum number of nodes at any level, which in a balanced tree is O(n) in the last level? Actually, the maximum number of nodes at any level in a balanced tree is about n/2, so O(n). But in a skewed tree, BFS would use O(1) at each level? Wait, in a skewed tree, BFS would have at most 1 node in the queue at a time? Actually, in a skewed tree (like a linked list), BFS would have at most 1 node in the queue because we dequeue one and enqueue one (its child). So the maximum queue size is 1? But wait, we start with root, then we dequeue root and enqueue its child, then dequeue that and enqueue its child, so at most 1 node in the queue. So for a skewed tree, BFS uses O(1) space? Actually, no: in the beginning, we have root in the queue (1). Then we dequeue root and enqueue its child (1). So yes, O(1). But in a balanced tree, the last level can have up to n/2 nodes, so O(n). So BFS worst-case space is O(n) for a balanced tree, while DFS (with a stack) in a balanced tree uses O(log n). So DFS is better in terms of space for balanced trees? Actually, for a balanced tree, the height is log n, so the stack will have at most log n nodes at a time? Wait, in DFS, we push one path at a time. In a balanced tree, the longest path from root to leaf is log n, so the stack will have at most log n nodes. But in a skewed tree, the stack will have n nodes. So both have worst-case O(n) for a skewed tree. But for a balanced tree, DFS is O(log n) and BFS is O(n). So DFS is better in terms of space for balanced trees.

    However, we are using DFS with a stack (iterative) and we are pushing both children? Actually, in our code, we push the right child and then the left child. So at any time, the stack holds the nodes that are yet to be processed along one branch and the siblings of the nodes on that branch? Actually, the maximum size of the stack is the height of the tree? Not exactly, because we push both children and then pop one. But in the worst case (a tree that is a chain to the left), we push root, then push right (none) and left (the next node). Then we pop the left node (which is the next node) and then push its right (none) and left (next). So the stack never has more than 1 node? Wait, let's simulate:

        Tree: 1 -> 2 -> 3 -> 4 (all left children)
    
        Start: stack = [1]
        Pop 1 -> push right (none) and left (2) -> stack = [2]
        Pop 2 -> push right (none) and left (3) -> stack = [3]
        Pop 3 -> push right (none) and left (4) -> stack = [4]
        Pop 4 -> leaf -> total=4 -> stack empty.
    
        So stack size never exceeds 1.
    
        But what about a tree with both left and right?
    
        Example: 
             1
            / \
           2   3
          / \
         4   5
    
        We push 1 -> stack=[1]
        Pop 1 -> push 3, then push 2 -> stack=[3,2]  (size 2)
        Pop 2 -> push 5, then push 4 -> stack=[3,5,4] (size 3)
        Pop 4 -> leaf -> stack=[3,5]
        Pop 5 -> leaf -> stack=[3]
        Pop 3 -> leaf -> stack empty.
    
        So the maximum stack size was 3, which is the number of nodes in the longest path? Actually, the longest path from root to leaf is 3 (1->2->4 or 1->2->5). But we had 3 nodes in the stack at one point (when we had 3,5,4). Actually, the stack at that moment had 3 nodes: 3 (right child of root), 5 (right child of 2), and 4 (left child of 2). So it's not exactly the height. The height is 3 (if we count edges) or 3 (if we count nodes). But note: the stack can have more than the height because we push both children and then process one. In the worst case, the stack can have up to the number of nodes in the tree? Actually, no, because we are popping and then pushing. But consider a complete binary tree of height h (with 2^h -1 nodes). The maximum stack size? When we start at root, we push root. Then we pop root and push its right and left. Then we pop left (of root) and push its right and left. So at the moment we are processing the leftmost path, the stack has the right siblings of the nodes on the leftmost path. So the maximum stack size is the height? Actually, in a complete binary tree, when we are at the deepest leftmost leaf, the stack will have the right siblings of all the nodes on the path from the root to that leaf. How many? For a tree of height h (with h levels, root at level 1), the leftmost leaf is at level h. The right siblings: at each level, there is one right sibling. So total h nodes? Actually, for the leftmost leaf, the stack will have the right child of the root, the right child of the left child of the root, ... until the right child of the node at level h-1? That's h-1 nodes? Plus the leaf we are about to pop? Actually, when we are at the leaf, we pop it and then we don't push anything. So the stack before popping the leaf has the right siblings of the nodes on the path. So for a complete binary tree, the maximum stack size is h (if we count the root's right child, then the left child's right child, etc.). Actually, let's take h=3:
    
        Tree:
            1
           / \
          2   3
         / \
        4   5
    
        We push 1 -> stack=[1]
        Pop 1 -> push 3,2 -> stack=[3,2] (size 2)
        Pop 2 -> push 5,4 -> stack=[3,5,4] (size 3)
        Then we pop 4 (leaf) -> stack=[3,5] (size 2)
        Pop 5 -> stack=[3] (size 1)
        Pop 3 -> stack empty.
    
        So maximum size was 3, which is the number of nodes in the longest path? Actually, the longest path has 3 nodes (1->2->4). But the stack had 3 nodes when we had 3,5,4. That's 3 nodes, but note that 3 is not on the path to 4? Actually, 3 is the right child of the root, which is a sibling of 2. So the stack can have up to the number of nodes in the tree? In this case, we had 3 nodes in the stack, but the tree has 5 nodes. So not all nodes.
    
        In the worst case, for a tree that is a chain to the left, the stack never has more than 1 node. For a tree that is a chain to the right? Let's try:
    
        Tree:
            1
             \
              2
               \
                3
                 \
                  4
    
        We push 1 -> stack=[1]
        Pop 1 -> push right (2) and left (none) -> stack=[2] (size 1)
        Pop 2 -> push right (3) -> stack=[3] (size 1)
        ... so always 1.
    
        So the worst-case stack size for a skewed tree (either left or right) is 1? Actually, in the left-skewed tree we had:
    
            1
           /
          2
         /
        3
    
        We push 1 -> stack=[1]
        Pop 1 -> push right (none) and left (2) -> stack=[2]
        Pop 2 -> push right (none) and left (3) -> stack=[3]
        Pop 3 -> leaf -> stack empty.
    
        So indeed, for a skewed tree, the stack size never exceeds 1? But wait, what if the tree is:
    
            1
           / \
          2   3
         /     \
        4       5
    
        This is not a chain, but a tree with two long branches.
    
        Push 1 -> stack=[1]
        Pop 1 -> push 3,2 -> stack=[3,2] (size 2)
        Pop 2 -> push right (none) and left (4) -> stack=[3,4] (size 2)
        Pop 4 -> leaf -> stack=[3] (size 1)
        Pop 3 -> push right (5) and left (none) -> stack=[5] (size 1)
        Pop 5 -> leaf -> stack empty.
    
        So maximum size 2.
    
        What about:
    
            1
           / \
          2   3
         / \   \
        4   5   6
    
        Push 1 -> stack=[1]
        Pop 1 -> push 3,2 -> stack=[3,2] (size 2)
        Pop 2 -> push 5,4 -> stack=[3,5,4] (size 3)
        Pop 4 -> leaf -> stack=[3,5] (size 2)
        Pop 5 -> leaf -> stack=[3] (size 1)
        Pop 3 -> push 6 -> stack=[6] (size 1)
        Pop 6 -> leaf -> stack empty.
    
        Maximum size 3.
    
        So the maximum stack size is the maximum number of nodes that are on the current path and the right siblings of the nodes on that path? Actually, it's the number of nodes that we have started but not finished. In the worst case, it can be the number of nodes in the tree? Let's try a tree that is a complete binary tree of height 3 (7 nodes):
    
        Tree:
               1
             /   \
            2     3
           / \   / \
          4   5 6   7
    
        Steps:
    
        Push 1 -> stack=[1] (size1)
        Pop 1 -> push 3,2 -> stack=[3,2] (size2)
        Pop 2 -> push 5,4 -> stack=[3,5,4] (size3)
        Pop 4 -> leaf -> stack=[3,5] (size2)
        Pop 5 -> leaf -> stack=[3] (size1)
        Pop 3 -> push 7,6 -> stack=[7,6] (size2)
        Pop 6 -> leaf -> stack=[7] (size1)
        Pop 7 -> leaf -> stack empty.
    
        Maximum size: 3.
    
        Now, what about a tree that is a complete binary tree of height 4 (15 nodes)? The maximum stack size would be? Let's think:
    
        We start at root, then push root's right and left -> 2 nodes.
        Then we process the left subtree: we pop the left child of root, then push its right and left -> now we have the root's right and the left child's right and left -> 3 nodes.
        Then we process the leftmost leaf of the left subtree: we pop the left child's left, which is a leaf? Actually, at the next step we pop the left child's left (which is a node at level 3) and then push its children (level 4). So at that moment, we have: root's right (level2), left child's right (level3), and the left child's left's children (level4). That's 3 nodes? Wait, we are popping the left child's left (level3) and then pushing its two children (level4). So the stack before popping the level3 node had: root's right (level2), left child's right (level3). Then we pop the left child's left (level3) and push its two children (level4). So then the stack has: root's right (level2), left child's right (level3), and the two children of the left child's left (level4). That's 4 nodes.
    
        So for a complete binary tree of height 4, the maximum stack size might be 4? Let's simulate:
    
        Tree of height 4 (with 15 nodes). We are interested in the leftmost path:
    
        Level1: root (1)
        Level2: left child (2)
        Level3: left child of 2 (4)
        Level4: left child of 4 (8) -> leaf.
    
        At the moment we are about to pop node 8 (leaf), the stack has:
    
        We pushed 1 -> stack=[1]
        Pop 1 -> push 3,2 -> stack=[3,2]
        Pop 2 -> push 5,4 -> stack=[3,5,4]
        Pop 4 -> push 7,6? Wait, no: node 4 has left and right? In a complete binary tree, node 4 (which is the left child of 2) has two children: 8 and 9? Actually, in a complete binary tree, the nodes are filled level by level. So:
    
        Level1: 1
        Level2: 2,3
        Level3: 4,5,6,7
        Level4: 8,9,10,11,12,13,14,15
    
        But note: node 4 is at level3 and has two children: 8 and 9.
    
        So when we pop node 4, we push its right (9) and left (8). Then the stack becomes: [3,5,9,8] (because we had [3,5,4] and then we pop 4 and push 9 and 8). So now the stack has 4 nodes: 3,5,9,8.
    
        Then we pop 8 (leaf) -> stack=[3,5,9] (size3)
        Then pop 9 (leaf) -> stack=[3,5] (size2)
        Then pop 5 (leaf? Wait, node 5 is at level3 and has two children? Actually, in a complete binary tree, node 5 has children 10 and 11. So when we pop 5, we push 11 and 10. Then the stack becomes: [3,11,10] (size3). Then we pop 10 (leaf), then 11 (leaf), then pop 3 -> push 7 and 6? Wait, node 3 has children 6 and 7. Then we push 7 and 6 -> stack=[7,6] (size2). Then pop 6 (leaf) -> stack=[7] (size1). Then pop 7 (leaf) -> stack empty.
    
        So the maximum stack size was 4.
    
        So for a complete binary tree of height h, the maximum stack size is h? In this case, h=4 (if we count the root as level1, then the leaf at level4). We had 4 nodes in the stack at one point.
    
        Actually, the maximum stack size in this DFS (pre-order) for a complete binary tree is the height of the tree? Let's think: when we are at the deepest leftmost leaf, the stack contains the right siblings of every node on the path from the root to that leaf. For a complete binary tree, each node on the path (except the leaf) has a right sibling? Actually, the root has a right sibling? No, the root is alone at level1. The left child of the root (node2) has a right sibling (node3). Then node2's left child (node4) has a right sibling (node5). Then node4's left child (node8) is a leaf and has no children. So the stack at the moment we are about to pop node8 has:
    
        - node3 (right sibling of node2)
        - node5 (right sibling of node4)
        - node9 (right child of node4) -> but note, node9 is the right child of node4, not a sibling of node4? Actually, node9 is the right child of node4, so it's a sibling of node8? But we pushed node9 when we processed node4. So the stack at that moment has:
    
          node3 (from root's right)
          node5 (from node2's right)
          node9 (from node4's right)
    
        and then we are about to pop node8.
    
        So that's 3 nodes? But we had 4: [3,5,9,8]. Actually, node8 is also in the stack until we pop it.
    
        So the maximum number of nodes in the stack is the number of nodes on the path from the root to the current node (including the current node) plus the right siblings of the nodes on that path (except the current node?).
    
        In the worst case, for a complete binary tree, the maximum stack size is the number of nodes in the longest path? Actually, in the example, the longest path has 4 nodes (1,2,4,8) and we had 4 nodes in the stack (1,2,4,8? No, we didn't have 1 and 2 and 4? Wait, we popped 1, then 2, then 4. So at the moment we are about to pop 8, the stack has 3,5,9,8. That's 4 nodes, but only 8 is on the path? Actually, 3 and 5 and 9 are not on the path to 8. They are right siblings (or right children of nodes on the path?).
    
        So it's not simply the height.
    
        However, note that the stack can never have more than the total number of nodes, and in the worst case (a tree that is a star? Actually, a tree where every node has two children until the leaves) the stack can hold up to the number of nodes in the tree? Let's try a tree that is a full binary tree with 3 levels (7 nodes). We already did and the maximum was 3? Actually, in the 7-node example, the maximum was 3? Wait, in the 7-node example (height 3), we had:
    
        Push 1 -> stack=[1] (size1)
        Pop 1 -> push 3,2 -> stack=[3,2] (size2)
        Pop 2 -> push 5,4 -> stack=[3,5,4] (size3)
        Pop 4 -> stack=[3,5] (size2)
        ... so maximum 3.
    
        For the 15-node example, we had 4.
    
        So it seems the maximum stack size is the height of the tree? Because for a tree of height h, the maximum stack size we observed was h? In the 15-node tree, h=4 (if we count the root as level1 and the leaf as level4). We had 4.
    
        But wait, in the 15-node tree, the leaf at level4 (node8) and we had 4 nodes in the stack? Actually, we had 4 nodes: 3,5,9,8. But 8 is the leaf we are about to pop, so the stack has 4 nodes including the leaf? Yes.
    
        So the maximum stack size is the height of the tree? Let's test with a tree of height 5 (31 nodes). I think it would be 5.
    
        Why? Because when we are at the leftmost leaf, we have pushed the right siblings of all the nodes on the path (which are at levels 2,3,4) and the right child of the node at level4? Actually, the node at level4 (the parent of the leaf) has a right child? In a complete binary tree, the leftmost leaf at level5 is the left child of a node at level4. That node at level4 has a right child (which is the right sibling of the leaf). So we have:
    
          root's right (level2)
          node2's right (level3)
          node4's right (level4)
          node8's right? Actually, node8 is the leaf and has no children, so we don't push from node8.
    
        But when we popped node4, we pushed its right child (node9). Then when we popped node2, we pushed node5. Then when we popped root, we pushed node3. So at the moment we are about to pop node8, the stack has:
    
          node3 (level2)
          node5 (level3)
          node9 (level4)
    
        and node8 (level5) is also in the stack? Actually, we pushed node8 when we processed node4. So the stack has:
    
          node3, node5, node9, node8.
    
        That's 4 nodes? But the height is 5? Wait, the leaf is at level5, but we have 4 nodes in the stack? Actually, we have:
    
          level2: node3
          level3: node5
          level4: node9
          level5: node8
    
        So that's 4 nodes, but the leaf is at level5. So the stack has nodes from levels 2,3,4,5. That's 4 levels? But the tree has 5 levels. So the stack size is 4, which is the height-1? Or the number of nodes on the path from the root to the leaf? The path from root to node8 is: 1 (level1), 2 (level2), 4 (level3), 8 (level4)? Wait, if the leaf is at level5, then the path has 5 nodes? Actually, in a tree of height 5, the root is at level1, then level2, level3, level4, level5. So the path from root to a leaf at level5 has 5 nodes.
    
        But in our example, we had:
    
        level1: root (1)
        level2: node2 (left child of root) and node3 (right child of root)
        level3: for node2: left child 4, right child 5.
        level4: for node4: left child 8, right child 9.
        level5: for node8: left child? Actually, in a complete binary tree of height 5, the leaves are at level5. So node8 is at level4? Wait, let's define:
    
        Height of a tree: number of edges from root to the deepest leaf. Or number of levels? Sometimes height is defined as the number of nodes on the longest path. In our example, we said the tree has 15 nodes and height 4? Actually, a complete binary tree with 15 nodes has 4 levels (root at level1, then 2,3,4). So the leaves are at level4. So the height (in terms of edges) is 3? Or in terms of nodes, it's 4.
    
        To avoid confusion, let's define:
    
        - The root is at depth 0 or 1? We are talking about the number of nodes in the path.
    
        In the 15-node tree, the longest path from root to leaf has 4 nodes (root, then level2, level3, leaf at level4). So the height (number of nodes) is 4.
    
        In the 7-node tree, the longest path has 3 nodes.
    
        In the 3-node tree (root with two children), the longest path has 2 nodes? Actually, the root and then a leaf? That's 2 nodes, so height=2.
    
        So in our examples, the maximum stack size was equal to the height (number of nodes in the longest path).
    
        Why? Because when we are at the leftmost leaf, the stack contains:
    
          - the right child of the root (which is at level2)
          - the right child of the left child of the root (which is at level3)
          - ... until the right child of the node at level (h-1) (which is at level h? Actually, the node at level h-1 has a right child that is at level h? But note: the leaf we are at is at level h, and it is the left child of its parent (at level h-1). The parent has a right child (at level h) that we pushed. So that right child is at the same level as the leaf? Then when we pop the leaf, we have that right child (at level h) in the stack? Actually, the leaf is at level h, and the right child of the parent (which is at level h) is a leaf? Not necessarily, if the tree is not complete? But in a complete tree, it is.
    
        So the stack at the moment we are about to pop the leftmost leaf (at level h) has:
    
          - one node from level2 (the root's right child)
          - one node from level3 (the right child of the node at level2 on the leftmost path)
          - ...
          - one node from level h (the right child of the node at level h-1 on the leftmost path)
          - and the leftmost leaf itself (at level h)
    
        So that's (h-1) nodes from levels 2 to h, plus the leaf at level h? Actually, the leaf is at level h, so we have:
    
          level2: 1 node
          level3: 1 node
          ...
          level h: 2 nodes? (the right child of the parent and the leaf itself)
    
        Wait, the leaf is at level h, and the right child of the parent (which is at level h-1) is also at level h? So we have two nodes at level h? Then the total is (h-1) + 1? Actually, the levels from 2 to h-1: that's (h-2) nodes? Let's count:
    
        For h=4 (15-node tree):
    
          level2: node3 (1 node)
          level3: node5 (1 node)
          level4: node9 (right child of node4) and node8 (leaf) -> 2 nodes.
    
          Total: 1+1+2 = 4.
    
        But the height (number of nodes in the longest path) is 4. So 4 nodes.
    
        For h=3 (7-node tree):
    
          level2: node3 (1 node)
          level3: node5 (right child of node2) and node4 (leaf? Actually, in the 7-node tree, node4 is at level3 and is a leaf? Wait, the 7-node tree:
    
               1
             /   \
            2     3
           / \   / \
          4   5 6   7
    
          The leftmost leaf is node4 (at level3). When we are about to pop node4, the stack has:
    
            node3 (level2)
            node5 (level3, right child of node2)
            node4 (level3, the leaf)
    
          So that's 3 nodes, and the height is 3.
    
        So it seems the maximum stack size is the height (number of nodes in the longest path).
    
        Why? Because we are traversing in a depth-first manner and we are pushing the right child before the left child. So when we go down the leftmost path, we are pushing the right child of each node on that path. Then when we reach the leaf, the stack has the right child of every node on the path (except the leaf, because the leaf has no children) and also the leaf itself? Actually, the leaf is pushed when we process its parent. So the stack at the moment we are about to pop the leaf has:
    
          - the right child of the root (if exists) -> one node at level2
          - the right child of the left child of the root (if exists) -> one node at level3
          - ... until the right child of the parent of the leaf (which is at level h-1) -> one node at level h
          - and the leaf itself (at level h) that we pushed when processing the parent.
    
        So that's (h-1) nodes from levels 2 to h (the right children) plus the leaf at level h? Actually, the leaf is at level h, and the right child of the parent is also at level h? So we have two nodes at level h? Then the total is (h-1) + 1? Wait, the right child of the parent is at level h, and the leaf is at level h? Then we have two nodes at level h? But in the example, for h=4, we had:
    
          level2: 1 node (node3)
          level3: 1 node (node5)
          level4: 2 nodes (node9 and node8)
    
        So total 4.
    
        But note: the leaf (node8) is at level4, and node9 (right child of node4) is also at level4. So that's two nodes at the last level.
    
        So the maximum stack size is the number of nodes in the longest path? Actually, the longest path has 4 nodes (1,2,4,8). But we have 4 nodes in the stack? They are not the same nodes. The nodes in the stack are: 3,5,9,8. That's 4 nodes, but the longest path nodes are 1,2,4,8. So the stack has 4 nodes, but only one (node8) is on the longest path? The others are right siblings.
    
        So it's not the same.
    
        However, in terms of big O, the maximum stack size is O(h) because the number of right siblings on the leftmost path is at most h (actually, h-1). And the leaf itself is one more? So total O(h).
    
        But wait, in the worst case, the tree could be such that every node on the leftmost path has a right child, and those right children are long chains? Then the stack would have:
    
          root's right child (which might have a long chain) -> but we only push the immediate right child of the root, and then when we process that right child, we push its children? Actually, we are doing DFS and we push the immediate children. So when we push the root's right child, and then we go down the leftmost path of the entire tree, we are not processing the root's right child until we finish the leftmost path? Wait, we are pushing the root's right child and then the left child of the root. Then we pop the left child and go down its leftmost path. So the root's right child sits in the stack until we finish the entire left subtree? Then we process the root's right child and its subtree.
    
        So the stack will have:
    
          - the root's right child (and then when we process the left subtree, we push more nodes on top of it)
    
        So the stack can have:
    
          root's right child (at level2)
          then, when we go down the left subtree, we push the right child of the left child of the root (at level3) and then the left child of that, etc.
    
        So the stack will have at most:
    
          one node from level2 (the root's right child)
          one node from level3 (the right child of the left child of the root)
          one node from level4 (the right child of the left child of the left child of the root)
          ... until we reach the leaf.
    
        So that's (h-1) nodes? And then the leaf itself? Actually, the leaf is pushed by its parent, so when we are about to pop the leaf, the leaf is in the stack. So the stack has:
    
          the root's right child (level2)
          the right child of the left child of the root (level3)
          ...
          the right child of the node at level h-1 (which is at level h)
          and the leaf (at level h)
    
        So that's (h-1) + 1 = h nodes.
    
        Therefore, the maximum stack size is h, the height (number of nodes in the longest path).
    
        So the space complexity is O(h).
    
        In the worst case, h can be n (for a skewed tree), so O(n). In a balanced tree, h is O(log n).
    
        So the iterative DFS has the same space complexity as the recursive DFS (which also uses O(h) for the call stack).
    
        Therefore, both are acceptable.
    
        Since the iterative version avoids recursion and the potential recursion limit, I'll write the iterative version.
    
        But note: the iterative version uses a stack that we manage, so we are not limited by the recursion limit.
    
        However, in Python, the recursion limit is usually around 1000, so for trees with height >1000, recursive would fail.
    
        So I'll write the iterative version.
    
        Code:
    
        def sum_of_leaves(root):
            if not root:
                return 0
            stack = [root]
            total = 0
            while stack:
                node = stack.pop()
                if node.left is None and node.right is None:
                    total += node.val
                if node.right:
                    stack.append(node.right)
                if node.left:
                    stack.append(node.left)
            return total
    
        This is the function.
    
        Now, let's write the explanation.
    
        Explanation:
    
        We use an iterative depth-first search (DFS) with a stack. We start by pushing the root node onto the stack. Then, while the stack is not empty, we pop a node. If the node is a leaf (both left and right are None), we add its value to the total. Then, we push the right child first and then the left child onto the stack. This ensures that the left subtree is processed before the right subtree (since stack is LIFO). However, the order of processing does not affect the sum. We continue until the stack is empty. The time complexity is O(n) because we visit each node exactly once. The space complexity is O(h), where h is the height of the tree, because the stack will hold at most h nodes at any time (in the worst case, when the tree is a straight line, the stack will hold at most 1 node? Actually, in a skewed tree, the stack never holds more than 1 node? Wait, in a left-skewed tree, we push the left child and then pop it, so the stack size is at most 1. But in a balanced tree, the stack can hold up to h nodes. So the space complexity is O(h). In the worst case, h can be n (for a tree that is a chain), but note: in a chain, the stack never has more than 1 node? Let's re-examine:
    
          Left-skewed tree: 
               1
              /
             2
            /
           3
    
          Steps:
            push 1 -> stack=[1] (size1)
            pop 1 -> push right (none) and left (2) -> stack=[2] (size1)
            pop 2 -> push right (none) and left (3) -> stack=[3] (size1)
            pop 3 -> leaf -> stack empty.
    
          So the stack size never exceeds 1. But wait, what about a tree that is a chain to the right? Same.
    
          What about a tree that is:
    
               1
                \
                 2
                  \
                   3
    
          Same: stack size at most 1.
    
          So for a skewed tree (either left or right), the stack size is 1? Actually, if the tree is left-skewed, we push the left child and then pop it, so the stack has only the current node? But what if the tree is:
    
               1
              / \
             2   3
            /     \
           4       5
    
          We push 1 -> stack=[1]
          pop 1 -> push 3,2 -> stack=[3,2] (size2)
          pop 2 -> push right (none) and left (4) -> stack=[3,4] (size2)
          pop 4 -> leaf -> stack=[3] (size1)
          pop 3 -> push right (5) -> stack=[5] (size1)
          pop 5 -> leaf -> stack empty.
    
          So maximum size 2.
    
          So the worst-case stack size is the maximum number of nodes that are on the current path and the right siblings of the nodes on that path? In the above, the leftmost path is 1->2->4. The right siblings: 3 (right of 1) and then when we are at 2, we don't have a right sibling for 2? Actually, 2's right sibling is 3? But 3 is already in the stack. Then when we go to 4, 4 has no right sibling? So the stack at the moment we are about to pop 4 has 3 and 4? That's 2 nodes.
    
          So the worst-case stack size is the length of the longest path? In the above, the longest path has 3 nodes (1,2,4) and the stack had 2 nodes? Actually, 3 and 4 are two nodes. So not exactly.
    
          Let me think of a tree where the stack might be larger. Consider:
    
               1
             /   \
            2     3
           / \   / \
          4   5 6   7
         /         \
        8           9
    
        The leftmost path: 1->2->4->8 (4 nodes). When we are about to pop 8, the stack has:
    
          We pushed 1 -> stack=[1]
          Pop 1 -> push 3,2 -> stack=[3,2]
          Pop 2 -> push 5,4 -> stack=[3,5,4]
          Pop 4 -> push right (none) and left (8) -> stack=[3,5,8]
          Now we are about to pop 8.
    
          So the stack has 3 nodes: 3,5,8.
    
          The longest path has 4 nodes (1,2,4,8). But we have 3 nodes in the stack.
    
          What about the right child of node2? That's node5, which is at the same level as node4? And then node8 is the left child of node4.
    
          So the stack has:
    
            node3 (level2)
            node5 (level3)
            node8 (level4)
    
          That's 3 nodes, but the leaf is at level4. So the stack has nodes from levels 2,3,4.
    
          The longest path has nodes from levels 1,2,3,4. So we are missing the root? Because we already popped the root.
    
          So the stack at that moment has the right siblings of the nodes on the path (except the root, because the root was popped) and the leaf? Actually, the root's right child (node3) is in the stack, the right child of node2 (node5) is in the stack, and the leaf (node8) is in the stack. So that's 3 nodes.
    
          So the maximum stack size is the number of nodes on the path from the root to the leaf (excluding the root) plus the leaf? That would be (h-1) + 1 = h? But in this case, h=4 (if we count the root as level1 and the leaf as level4) and we have 3 nodes in the stack? So it's h-1.
    
          Actually, the root is not in the stack because we popped it. So the stack has:
    
            the right child of the root (if exists) -> level2
            the right child of the left child of the root (if exists) -> level3
            ... until the right child of the parent of the leaf (if exists) -> level h
            and the leaf itself (level h)
    
          But note: the leaf is the left child of its parent, so the parent's right child is at the same level as the leaf? Then we have two nodes at level h? So the total is:
    
            (h-2) nodes from levels 2 to h-1 (the right children of the nodes on the path except the parent of the leaf) 
            + 1 node (the right child of the parent of the leaf, at level h)
            + 1 node (the leaf itself, at level h)
    
          That's (h-2) + 2 = h.
    
          In the example, h=4, so we should have 4 nodes? But we had 3. Why? Because the parent of the leaf (node4) does not have a right child? In the example, node4 has no right child. So we don't push a right child for node4. Then the stack at the moment we are about to pop node8 has:
    
            node3 (level2)
            node5 (level3)  -> because node2 has a right child (node5)
            node8 (level4)
    
          So that's 3 nodes.
    
          So the formula is:
    
          Let the leftmost path be: root (level1), node2 (level2), node4 (level3), node8 (level4).
    
          For each node on the path except the leaf (i.e., root, node2, node4):
    
            - For root: we pushed its right child (node3) and then we popped root, so node3 is in the stack.
            - For node2: we pushed its right child (node5) when we popped node2? Actually, when we popped node2, we pushed node5 and then node4. Then we popped node4 and pushed its left child (node8). So at the moment we are about to pop node8, the stack has node3 (from root), node5 (from node2), and node8.
    
          So for each node on the path except the leaf, we have one node in the stack (the right child of that node) if that right child exists. And then we have the leaf.
    
          So the number of nodes in the stack at that moment is:
    
            (number of nodes on the path that have a right child) + 1 (for the leaf)
    
          In the example, the path nodes that have a right child: root (has right child node3) and node2 (has right child node5). Node4 does not have a right child. So 2 + 1 = 3.
    
          In the complete binary tree example, every node on the path (except the leaf) has a right child? Actually, in a complete binary tree, every node except the leaves has two children. So for a path of length h (h nodes), we have (h-1) nodes that are not leaves (the first h-1 nodes) and each has a right child. So the stack would have:
    
            (h-1) right children (from the first h-1 nodes on the path) 
            and the leaf (the last node on the path)
    
            total = h.
    
          But wait, the leaf is on the path and we pushed it when we processed its parent. So the leaf is in the stack. And the right children of the first h-1 nodes are also in the stack. So that's (h-1) + 1 = h.
    
          In the complete binary tree of height 4 (15 nodes), h=4, so we expect 4 nodes in the stack. In our simulation, we had:
    
            When about to pop node8 (leaf), the stack had: node3, node5, node9, node8? Wait, node9 is the right child of node4 (which is the parent of node8). So:
    
            root (node1) has right child node3 -> in stack.
            node2 (left child of root) has right child node5 -> in stack.
            node4 (left child of node2) has right child node9 -> in stack.
            node8 (left child of node4) -> in stack.
    
          So that's 4 nodes: node3, node5, node9, node8.
    
          So indeed, h=4.
    
          Therefore, the maximum stack size is h.
    
          And h can be as large as n in the worst case (a tree that is a chain and every node has a right child? Actually, in a chain, the nodes don't have right children. So the maximum stack size in a chain is 1? Because we only have the current node in the stack? Wait, in a left-skewed chain, we push the left child and then pop it, so the stack size is 1. But if the chain is such that every node has a right child? That would not be a chain, because a chain by definition has at most one child. So if we have a tree that is a chain to the left but every node also has a right child? That would not be a chain. For example:
    
               1
              / \
             2   3
            /     \
           4       5
          /         \
         6           7
    
          This tree has a long left branch and a long right branch. The leftmost path is 1->2->4->6 (4 nodes). When we are about to pop 6, the stack has:
    
            We pushed 1 -> stack=[1]
            Pop 1 -> push 3,2 -> stack=[3,2]
            Pop 2 -> push 5,4 -> stack=[3,5,4]
            Pop 4 -> push right (none) and left (6) -> stack=[3,5,6]
    
          So the stack has 3 nodes: 3,5,6. The path length is 4, but we have 3 nodes in the stack? Because node2's right child (node5) is in the stack, and root's right child (node3) is in the stack, and the leaf (node6) is in the stack. So that's 3 nodes. And the path has 4 nodes? Actually, the path from root to node6 is 1->2->4->6 (4 nodes). But the stack has 3 nodes because node4 does not have a right child? So we didn't push a right child for node4.
    
          So the maximum stack size is the number of nodes on the path that have a right child, plus the leaf.
    
          In the worst case, if every node on the path (except the leaf) has a right child, then we have (h-1) + 1 = h.
    
          So the worst-case space complexity is O(h), and h can be O(n) in the worst-case tree (a tree that is a complete binary tree? Actually, in a complete binary tree, h is about log n, so O(log n). But in a tree that is a chain, h is n, but then the nodes on the chain don't have right children? So the stack size is 1? So the worst-case space complexity is O(n) when the tree is such that the leftmost path has every node having a right child? But if every node on the leftmost path has a right child, then the tree is not a chain, and the number of nodes on the leftmost path is at most the height, which can be O(n) if the tree is very unbalanced? For example, a tree that has a long left branch and at every node on that branch, there is a right child that is a leaf? Then the leftmost path has h nodes, and each of the first h-1 nodes has a right child (leaf). Then when we are about to pop the leftmost leaf, the stack has:
    
            the right child of the root (leaf) -> level2
            the right child of the left child of the root (leaf) -> level3
            ...
            the right child of the node at level h-1 (leaf) -> level h
            and the leftmost leaf (at level h)
    
          So that's h nodes? But note: the leftmost leaf is at level h, and the right children are at levels 2 to h. So the total number of nodes in the stack is (h-1) (from levels 2 to h-1) + 1 (the right child of the node at level h-1, which is at level h) + 1 (the leftmost leaf at level h) = h+1? Wait, let's count:
    
          Levels:
    
            level2: 1 node (right child of root)
            level3: 1 node (right child of node at level2)
            ...
            level h-1: 1 node (right child of node at level h-2)
            level h: 2 nodes (right child of node at level h-1 and the leftmost leaf)
    
          So total: (h-2) + 2 = h.
    
          So indeed, the maximum stack size is h.
    
          And h can be as large as n? For example, if the tree is a straight line to the left, then h = n, but then the nodes on the path (except the leaf) do not have right children? So the stack size would be 1. So the worst-case stack size of O(h) is not tight? Actually, the worst-case stack size is O(n) when the tree is such that the leftmost path has every node having a right child? But if every node on the leftmost path has a right child, then the number of nodes on the leftmost path is at most the height, but the height is the number of nodes on the longest path. So if we have a tree with a long left branch and at each node on that branch we have a right child that is a leaf, then the leftmost path has h nodes, and the total number of nodes in the tree is at least 2h-1? Actually, the root, then for each of the h-1 nodes on the leftmost path (except the leaf) we have a right child. So total nodes = h (leftmost path) + (h-1) (right children) = 2h-1. So h is about n/2. So the stack size is h, which is O(n).
    
          Therefore, the worst-case space complexity is O(n).
    
          But note: in the worst-case tree (a complete binary tree), h is O(log n), so the stack uses O(log n). In the worst-case space, we can have a tree that is a left chain with right children at every node, then h = n/2, so O(n).
    
          So the space complexity is O(n) in the worst case.
    
          But the recursive version also has O(h) space, which in the worst case is O(n).
    
          So both are acceptable.
    
          I think we are done.
    
          Let me write the iterative version.
    
          Code:
    
          def sum_of_leaves(root):
              if not root:
                  return 0
              stack = [root]
              total = 0
              while stack:
                  node = stack.pop()
                  if node.left is None and node.right is None:
                      total += node.val
                  if node.right:
                      stack.append(node.right)
                  if node.left:
                      stack.append(node.left)
              return total
    
          This is the function.
    
          Now, I'll write the explanation.
    
          However, note: the problem says "write a function", so I'll write the function and then the explanation.
    
          But the instruction says: "Please write a function that solves this problem, and explain your algorithm."
    
          So I'll write the function and then the explanation.
    
          Since the function is short, I'll write it first.
    
          Let me write:
    
          ```python
          def sum_of_leaves(root):
              if not root:
                  return 0
              stack = [root]
              total = 0
              while stack:
                  node = stack.pop()
                  if node.left is None and node.right is None:
                      total += node.val
                  if node.right:
                      stack.append(node.right)
                  if node.left:
                      stack.append(node.left)
              return total
          ```
    
          Explanation:
    
          We use an iterative depth-first search (DFS) approach. We initialize a stack with the root node. Then, we repeatedly pop a node from the stack. If the popped node is a leaf (i.e., it has no left or right child), we add its value to the total sum. Then, we push the right child followed by the left child onto the stack (if they exist). This order ensures that the left subtree is processed before the right subtree because the stack is last-in-first-out (LIFO). However, since we are only summing the leaf values, the order of traversal does not matter. We continue until the stack is empty.
    
          Time Complexity: O(n), where n is the number of nodes in the tree, because we visit each node exactly once.
    
          Space Complexity: O(h), where h is the height of the tree. In the worst case, the stack can hold up to h nodes. In a balanced tree, h is O(log n), but in the worst-case (a skewed tree), h can be O(n). However, note that in a skewed tree where every node has only one child, the stack size never exceeds 1. But in a tree where the leftmost path has many nodes that also have right children, the stack size can be up to h. Since h can be O(n) in the worst-case (for example, a tree with a long left branch and each node on that branch having a right child), the space complexity is O(n) in the worst case.
    
          Alternatively, we could use a recursive DFS, which would also have O(h) space complexity due to the recursion stack. The iterative approach avoids recursion and is generally safer for very deep trees.
    
          This completes the solution.
    
          But wait: what if the tree has negative values? We are just adding, so it's fine.
    
          We assume the node values are integers.
    
          So we are done.
    
          Let me write the code and explanation.
    
          However, note: the problem says "binary tree", so the tree is not necessarily a binary search tree.
    
          Our algorithm works for any binary tree.
    
          I think that's it.
    
          I'll now write the final answer.</think>
    

    We can solve this problem by traversing the tree and summing the values of all leaf nodes (nodes with no children). An iterative depth-first search (DFS) using a stack is effective and avoids recursion depth issues.

    Algorithm

    1. Initialize: Start with a stack containing the root node and a total sum set to 0.
    2. Traverse: While the stack is not empty:
      • Pop a node from the stack.
      • If the node is a leaf (both left and right are None), add its value to total.
      • Push the right child first (if exists), then the left child (if exists) onto the stack. This order ensures the left subtree is processed before the right due to the stack's LIFO nature, though the order doesn't affect the sum.
    3. Return: After traversal, return total.

    Complexity

    • Time: O(n), where n is the number of nodes—each node is visited once.
    • Space: O(h), where h is the tree height. The stack holds at most h nodes. In the worst case (e.g., a tree with a long left branch where each node has a right child), h can be O(n). For a balanced tree, h is O(log n).

    Solution Code

    def sum_of_leaves(root):
        if not root:
            return 0
        stack = [root]
        total = 0
        while stack:
            node = stack.pop()
            if node.left is None and node.right is None:
                total += node.val
            if node.right:
                stack.append(node.right)
            if node.left:
                stack.append(node.left)
        return total
    

    Explanation

    • Stack Usage: The stack tracks nodes to visit. We start with the root.
    • Leaf Check: When a node has no children, it's a leaf—its value contributes to the sum.
    • Child Push Order: Pushing the right child before the left ensures the left subtree is processed first (since the stack is LIFO). This order is arbitrary for summing but follows a standard DFS pattern.
    • Termination: The loop ends when all nodes are processed (stack empty), and the accumulated total is returned.

    This approach efficiently sums all leaf values without recursion, handling trees of any size safely.