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

Video Description

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. Check out my interview prep platform for learning the patterns! 📢 Interview Prep Platform: https://algoswithmichael.com 🔗 Social 🔗 🎧 Join the community Discord: https://discord.gg/aVWsAaaCtT 💰 Support me on Patreon: https://www.patreon.com/michaelmuinos 🔗Follow me on LinkedIn: https://www.linkedin.com/in/michael-muinos 📂Follow me on Github: https://github.com/MichaelMuinos ⭐️ Timestamps ⭐️ 00:00 - Intro 00:19 - Problem Overview 02:22 - Algorithm Walkthrough 07:35 - Code Walkthrough 10:52 - Time & Space Complexity