Binary Tree Maximum Path Sum (Animated Walkthrough) (LeetCode)

💰 Support me on Patreon: https://www.patreon.com/michaelmuinos
🔗Follow me on Twitter: https://twitter.com/MichaelMuinos
📂Follow me on Github: https://github.com/MichaelMuinos

00:00 - Intro
00:19 - Problem Overview
02:22 - Algorithm Walkthrough
07:35 - Code Walkthrough
10:52 - Time & Space Complexity

Binary Tree Maximum Path Sum is a popular LeetCode problem involving the knowledge of recursion, binary trees, and postorder traversal. This problem is asking at companies including Amazon, Google, Microsoft, Facebook, and Bloomberg.

For this problem, we are given a binary tree and must find the maximum path sum in the tree. A path sum is the sum of the values in a path of the binary tree. The binary tree can have negative numbers, thus our maximum does not necessarily have to be positive. To solve this efficiently, we must traverse each node in the tree computing the max sum at each step. If we encounter a negative number, we will bound that value to a zero to ensure that we always get the absolute maximum.

The time complexity of the solution will be linear because we must does each node in the tree in our traversal. The space complexity is going to be O(H) where H is the height of our tree. Since we are using recursion, in the worst case, we will have H recursive calls which will fill up our stack space.

Видео Binary Tree Maximum Path Sum (Animated Walkthrough) (LeetCode) канала Michael Muinos