Complexity of a Recursive Binary Tree Sum: Balanced Versus Skewed Trees

A recursive function computes the sum of all node values in a binary tree: ```python def tree_sum(node): if node is None: return 0 return node.val + tree_sum(node.left) + tree_sum(node.right) ``` What are its time and space complexity for a tree with $n$ nodes? How does the space complexity differ between a balanced tree and the worst-case tree shape? This was asked as a verbal question. ```hint Where the memory goes The function creates no data structures. Ask what is still held in memory while the deepest call is running. ``` ### Clarifying Questions - Should the space analysis include the call stack, or only memory the function allocates explicitly? - Can the tree be empty? ### What a Strong Answer Covers - Time complexity justified by counting calls, including the calls on empty children - Space complexity stated in terms of the tree height, with the reason - The balanced case and the degenerate chain case, with their bounds - Practical consequences of deep recursion, and an alternative that avoids it ### Follow-up Questions - The default recursion limit in Python is 1,000 frames. What happens on a 100,000-node chain, and how would you fix it? - Can you compute the sum with $O(1)$ extra space? What does that cost? - How do the bounds change for a tree in which each node can have any number of children?