##### ###### ##### ### # # ### # # ###### ## ## ## ## ## ## ## # # # # # ## ##### #### ##### # # # # # # # #### ## # ## ## ## ## # # # # # ## ## # ###### ## ### # ### # ######
##### ###### ##### ### # # ### # # ###### ## ## ## ## ## ## ## # # # # # ## ##### #### ##### # # # # # # # #### ## # ## ## ## ## # # # # # ## ## # ###### ## ### # ### # ######
Handling negative values
Negative nodes complicate things. We might want to exclude a subtree entirely if its contribution is negative. Trick: when computing , take . This lets us "cut off" negative subtrees. Base case: null node returns , . Leaf returns . Time: single post-order traversal. Space: for recursion stack where is tree height.
Time complexity: .
Space complexity: .
