{"id":1025,"date":"2025-09-01T13:58:36","date_gmt":"2025-09-01T08:28:36","guid":{"rendered":"https:\/\/codeanddebug.in\/blog\/?p=1025"},"modified":"2025-09-01T13:58:38","modified_gmt":"2025-09-01T08:28:38","slug":"binary-tree-maximum-path-sum","status":"publish","type":"post","link":"https:\/\/codeanddebug.in\/blog\/binary-tree-maximum-path-sum\/","title":{"rendered":"Binary Tree Maximum Path Sum | Leetcode 124 | Detailed Recursive Solution"},"content":{"rendered":"\n<p>You are given the root of a binary tree. Your task is to find the <strong>maximum path sum<\/strong> in the tree.<\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>A <strong>path<\/strong> is any sequence of nodes where each pair of adjacent nodes is connected by an edge.<\/li>\n\n\n\n<li>A path does not need to pass through the root.<\/li>\n\n\n\n<li>The path must contain <strong>at least one node<\/strong>.<\/li>\n<\/ul>\n\n\n\n<p>The path sum is the sum of the node values along that path.<br>We want to maximize this path sum.<\/p>\n\n\n\n<p>Here&#8217;s the [<strong><a href=\"https:\/\/leetcode.com\/problems\/binary-tree-maximum-path-sum\/description\/\" target=\"_blank\" rel=\"noreferrer noopener\"><mark style=\"background-color:rgba(0, 0, 0, 0)\" class=\"has-inline-color has-vivid-purple-color\"><span style=\"text-decoration: underline;\">Problem Link<\/span><\/mark><\/a><\/strong>] to begin with.<\/p>\n\n\n\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n\n\n\n<h3 class=\"wp-block-heading\">Examples<\/h3>\n\n\n\n<p><strong>Example 1<\/strong><\/p>\n\n\n\n<div class=\"wp-block-kevinbatdorf-code-block-pro cbp-has-line-numbers\" data-code-block-pro-font-family=\"Code-Pro-JetBrains-Mono\" style=\"font-size:.875rem;font-family:Code-Pro-JetBrains-Mono,ui-monospace,SFMono-Regular,Menlo,Monaco,Consolas,monospace;--cbp-line-number-color:#D4D4D4;--cbp-line-number-width:calc(1 * 0.6 * .875rem);line-height:1.5rem;--cbp-tab-width:2;tab-size:var(--cbp-tab-width, 2)\"><span style=\"display:block;padding:16px 0 0 16px;margin-bottom:-1px;width:100%;text-align:left;background-color:#1E1E1E\"><svg xmlns=\"http:\/\/www.w3.org\/2000\/svg\" width=\"54\" height=\"14\" viewBox=\"0 0 54 14\"><g fill=\"none\" fill-rule=\"evenodd\" transform=\"translate(1 1)\"><circle cx=\"6\" cy=\"6\" r=\"6\" fill=\"#FF5F56\" stroke=\"#E0443E\" stroke-width=\".5\"><\/circle><circle cx=\"26\" cy=\"6\" r=\"6\" fill=\"#FFBD2E\" stroke=\"#DEA123\" stroke-width=\".5\"><\/circle><circle cx=\"46\" cy=\"6\" r=\"6\" fill=\"#27C93F\" stroke=\"#1AAB29\" stroke-width=\".5\"><\/circle><\/g><\/svg><\/span><span role=\"button\" tabindex=\"0\" data-code=\"Input: root = [1,2,3]\n\n        1\n       \/ \\\n      2   3\n\nOutput: 6\nExplanation: The path 2 \u2192 1 \u2192 3 has sum 6.\" style=\"color:#D4D4D4;display:none\" aria-label=\"Copy\" class=\"code-block-pro-copy-button\"><svg xmlns=\"http:\/\/www.w3.org\/2000\/svg\" style=\"width:24px;height:24px\" fill=\"none\" viewBox=\"0 0 24 24\" stroke=\"currentColor\" stroke-width=\"2\"><path class=\"with-check\" stroke-linecap=\"round\" stroke-linejoin=\"round\" d=\"M9 5H7a2 2 0 00-2 2v12a2 2 0 002 2h10a2 2 0 002-2V7a2 2 0 00-2-2h-2M9 5a2 2 0 002 2h2a2 2 0 002-2M9 5a2 2 0 012-2h2a2 2 0 012 2m-6 9l2 2 4-4\"><\/path><path class=\"without-check\" stroke-linecap=\"round\" stroke-linejoin=\"round\" d=\"M9 5H7a2 2 0 00-2 2v12a2 2 0 002 2h10a2 2 0 002-2V7a2 2 0 00-2-2h-2M9 5a2 2 0 002 2h2a2 2 0 002-2M9 5a2 2 0 012-2h2a2 2 0 012 2\"><\/path><\/svg><\/span><pre class=\"shiki dark-plus\" style=\"background-color: #1E1E1E\" tabindex=\"0\"><code><span class=\"line\"><span style=\"color: #569CD6\">Input<\/span><span style=\"color: #D4D4D4\">: <\/span><span style=\"color: #CE9178\">root = [1,2,3]<\/span><\/span>\n<span class=\"line\"><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><span style=\"color: #B5CEA8\">1<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">       <\/span><span style=\"color: #CE9178\">\/ \\<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">      <\/span><span style=\"color: #CE9178\">2   3<\/span><\/span>\n<span class=\"line\"><\/span>\n<span class=\"line\"><span style=\"color: #569CD6\">Output<\/span><span style=\"color: #D4D4D4\">: <\/span><span style=\"color: #B5CEA8\">6<\/span><\/span>\n<span class=\"line\"><span style=\"color: #569CD6\">Explanation<\/span><span style=\"color: #D4D4D4\">: <\/span><span style=\"color: #CE9178\">The path 2 \u2192 1 \u2192 3 has sum 6.<\/span><\/span><\/code><\/pre><\/div>\n\n\n\n<p><strong>Example 2<\/strong><\/p>\n\n\n\n<div class=\"wp-block-kevinbatdorf-code-block-pro cbp-has-line-numbers\" data-code-block-pro-font-family=\"Code-Pro-JetBrains-Mono\" style=\"font-size:.875rem;font-family:Code-Pro-JetBrains-Mono,ui-monospace,SFMono-Regular,Menlo,Monaco,Consolas,monospace;--cbp-line-number-color:#D4D4D4;--cbp-line-number-width:calc(2 * 0.6 * .875rem);line-height:1.5rem;--cbp-tab-width:2;tab-size:var(--cbp-tab-width, 2)\"><span style=\"display:block;padding:16px 0 0 16px;margin-bottom:-1px;width:100%;text-align:left;background-color:#1E1E1E\"><svg xmlns=\"http:\/\/www.w3.org\/2000\/svg\" width=\"54\" height=\"14\" viewBox=\"0 0 54 14\"><g fill=\"none\" fill-rule=\"evenodd\" transform=\"translate(1 1)\"><circle cx=\"6\" cy=\"6\" r=\"6\" fill=\"#FF5F56\" stroke=\"#E0443E\" stroke-width=\".5\"><\/circle><circle cx=\"26\" cy=\"6\" r=\"6\" fill=\"#FFBD2E\" stroke=\"#DEA123\" stroke-width=\".5\"><\/circle><circle cx=\"46\" cy=\"6\" r=\"6\" fill=\"#27C93F\" stroke=\"#1AAB29\" stroke-width=\".5\"><\/circle><\/g><\/svg><\/span><span role=\"button\" tabindex=\"0\" data-code=\"Input: root = [-10,9,20,null,null,15,7]\n\n        -10\n        \/  \\\n       9    20\n           \/  \\\n          15   7\n\nOutput: 42\nExplanation: The path 15 \u2192 20 \u2192 7 has sum 42.\" style=\"color:#D4D4D4;display:none\" aria-label=\"Copy\" class=\"code-block-pro-copy-button\"><svg xmlns=\"http:\/\/www.w3.org\/2000\/svg\" style=\"width:24px;height:24px\" fill=\"none\" viewBox=\"0 0 24 24\" stroke=\"currentColor\" stroke-width=\"2\"><path class=\"with-check\" stroke-linecap=\"round\" stroke-linejoin=\"round\" d=\"M9 5H7a2 2 0 00-2 2v12a2 2 0 002 2h10a2 2 0 002-2V7a2 2 0 00-2-2h-2M9 5a2 2 0 002 2h2a2 2 0 002-2M9 5a2 2 0 012-2h2a2 2 0 012 2m-6 9l2 2 4-4\"><\/path><path class=\"without-check\" stroke-linecap=\"round\" stroke-linejoin=\"round\" d=\"M9 5H7a2 2 0 00-2 2v12a2 2 0 002 2h10a2 2 0 002-2V7a2 2 0 00-2-2h-2M9 5a2 2 0 002 2h2a2 2 0 002-2M9 5a2 2 0 012-2h2a2 2 0 012 2\"><\/path><\/svg><\/span><pre class=\"shiki dark-plus\" style=\"background-color: #1E1E1E\" tabindex=\"0\"><code><span class=\"line\"><span style=\"color: #569CD6\">Input<\/span><span style=\"color: #D4D4D4\">: <\/span><span style=\"color: #CE9178\">root = [-10,9,20,null,null,15,7]<\/span><\/span>\n<span class=\"line\"><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><span style=\"color: #B5CEA8\">-10<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><span style=\"color: #CE9178\">\/  \\<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">       <\/span><span style=\"color: #CE9178\">9    20<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">           <\/span><span style=\"color: #CE9178\">\/  \\<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">          <\/span><span style=\"color: #CE9178\">15   7<\/span><\/span>\n<span class=\"line\"><\/span>\n<span class=\"line\"><span style=\"color: #569CD6\">Output<\/span><span style=\"color: #D4D4D4\">: <\/span><span style=\"color: #B5CEA8\">42<\/span><\/span>\n<span class=\"line\"><span style=\"color: #569CD6\">Explanation<\/span><span style=\"color: #D4D4D4\">: <\/span><span style=\"color: #CE9178\">The path 15 \u2192 20 \u2192 7 has sum 42.<\/span><\/span><\/code><\/pre><\/div>\n\n\n\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n\n\n\n<h2 class=\"wp-block-heading\">Intuition and Approach<\/h2>\n\n\n\n<p>This problem is trickier than a simple tree sum because a maximum path can:<\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>lie entirely in the left subtree,<\/li>\n\n\n\n<li>lie entirely in the right subtree,<\/li>\n\n\n\n<li>or pass through the current node (taking both left and right branches).<\/li>\n<\/ul>\n\n\n\n<p>To solve this, we need to consider two things for each node:<\/p>\n\n\n\n<ol class=\"wp-block-list\">\n<li><strong>Best path sum passing <em>through<\/em> this node<\/strong> (potential candidate for global maximum).\n<ul class=\"wp-block-list\">\n<li>This is <code>leftPathSum + node.val + rightPathSum<\/code>.<\/li>\n\n\n\n<li>It means: take the best contribution from the left, the best contribution from the right, and include the current node.<\/li>\n<\/ul>\n<\/li>\n\n\n\n<li><strong>Best path sum going <em>downward<\/em> from this node (to return to parent)<\/strong>.\n<ul class=\"wp-block-list\">\n<li>Since we can only extend in one direction upwards, we take the larger of left or right plus the node value:<\/li>\n\n\n\n<li><code>max(leftPathSum, rightPathSum) + node.val<\/code>.<\/li>\n<\/ul>\n<\/li>\n<\/ol>\n\n\n\n<p>Key trick:<\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>If a subtree gives a negative sum, we <strong>ignore it<\/strong> by treating it as 0, because adding it would only decrease the total.<\/li>\n<\/ul>\n\n\n\n<p>We keep a global variable <code>maxi<\/code> to store the maximum path sum encountered so far.<\/p>\n\n\n\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n\n\n\n<h2 class=\"wp-block-heading\">Code Implementation<\/h2>\n\n\n\n<div class=\"wp-block-kevinbatdorf-code-block-pro cbp-has-line-numbers\" data-code-block-pro-font-family=\"Code-Pro-JetBrains-Mono\" style=\"font-size:.875rem;font-family:Code-Pro-JetBrains-Mono,ui-monospace,SFMono-Regular,Menlo,Monaco,Consolas,monospace;--cbp-line-number-color:#D4D4D4;--cbp-line-number-width:calc(2 * 0.6 * .875rem);line-height:1.5rem;--cbp-tab-width:2;tab-size:var(--cbp-tab-width, 2)\"><span style=\"display:block;padding:16px 0 0 16px;margin-bottom:-1px;width:100%;text-align:left;background-color:#1E1E1E\"><svg xmlns=\"http:\/\/www.w3.org\/2000\/svg\" width=\"54\" height=\"14\" viewBox=\"0 0 54 14\"><g fill=\"none\" fill-rule=\"evenodd\" transform=\"translate(1 1)\"><circle cx=\"6\" cy=\"6\" r=\"6\" fill=\"#FF5F56\" stroke=\"#E0443E\" stroke-width=\".5\"><\/circle><circle cx=\"26\" cy=\"6\" r=\"6\" fill=\"#FFBD2E\" stroke=\"#DEA123\" stroke-width=\".5\"><\/circle><circle cx=\"46\" cy=\"6\" r=\"6\" fill=\"#27C93F\" stroke=\"#1AAB29\" stroke-width=\".5\"><\/circle><\/g><\/svg><\/span><span role=\"button\" tabindex=\"0\" data-code=\"class Solution:\n    maxi = float(&quot;-inf&quot;)\n\n    def findMaxPathSum(self, root):\n        if not root:\n            return 0\n\n        # Recursively get max path sums from left and right children\n        leftPathSum = self.findMaxPathSum(root.left)\n        rightPathSum = self.findMaxPathSum(root.right)\n\n        # If a path contributes negatively, ignore it\n        if leftPathSum &lt; 0:\n            leftPathSum = 0\n        if rightPathSum &lt; 0:\n            rightPathSum = 0\n\n        # Update global maximum: best path that passes through this node\n        self.maxi = max(self.maxi, leftPathSum + root.val + rightPathSum)\n\n        # Return best single-branch path sum to parent\n        return max(leftPathSum, rightPathSum) + root.val\n\n    def maxPathSum(self, root: Optional[TreeNode]) -&gt; int:\n        self.findMaxPathSum(root)\n        return self.maxi\" style=\"color:#D4D4D4;display:none\" aria-label=\"Copy\" class=\"code-block-pro-copy-button\"><svg xmlns=\"http:\/\/www.w3.org\/2000\/svg\" style=\"width:24px;height:24px\" fill=\"none\" viewBox=\"0 0 24 24\" stroke=\"currentColor\" stroke-width=\"2\"><path class=\"with-check\" stroke-linecap=\"round\" stroke-linejoin=\"round\" d=\"M9 5H7a2 2 0 00-2 2v12a2 2 0 002 2h10a2 2 0 002-2V7a2 2 0 00-2-2h-2M9 5a2 2 0 002 2h2a2 2 0 002-2M9 5a2 2 0 012-2h2a2 2 0 012 2m-6 9l2 2 4-4\"><\/path><path class=\"without-check\" stroke-linecap=\"round\" stroke-linejoin=\"round\" d=\"M9 5H7a2 2 0 00-2 2v12a2 2 0 002 2h10a2 2 0 002-2V7a2 2 0 00-2-2h-2M9 5a2 2 0 002 2h2a2 2 0 002-2M9 5a2 2 0 012-2h2a2 2 0 012 2\"><\/path><\/svg><\/span><pre class=\"shiki dark-plus\" style=\"background-color: #1E1E1E\" tabindex=\"0\"><code><span class=\"line\"><span style=\"color: #569CD6\">class<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #4EC9B0\">Solution<\/span><span style=\"color: #D4D4D4\">:<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">    maxi = <\/span><span style=\"color: #4EC9B0\">float<\/span><span style=\"color: #D4D4D4\">(<\/span><span style=\"color: #CE9178\">&quot;-inf&quot;<\/span><span style=\"color: #D4D4D4\">)<\/span><\/span>\n<span class=\"line\"><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">    <\/span><span style=\"color: #569CD6\">def<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #DCDCAA\">findMaxPathSum<\/span><span style=\"color: #D4D4D4\">(<\/span><span style=\"color: #9CDCFE\">self<\/span><span style=\"color: #D4D4D4\">, <\/span><span style=\"color: #9CDCFE\">root<\/span><span style=\"color: #D4D4D4\">):<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><span style=\"color: #C586C0\">if<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #569CD6\">not<\/span><span style=\"color: #D4D4D4\"> root:<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">            <\/span><span style=\"color: #C586C0\">return<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #B5CEA8\">0<\/span><\/span>\n<span class=\"line\"><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><span style=\"color: #6A9955\"># Recursively get max path sums from left and right children<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        leftPathSum = <\/span><span style=\"color: #569CD6\">self<\/span><span style=\"color: #D4D4D4\">.findMaxPathSum(root.left)<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        rightPathSum = <\/span><span style=\"color: #569CD6\">self<\/span><span style=\"color: #D4D4D4\">.findMaxPathSum(root.right)<\/span><\/span>\n<span class=\"line\"><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><span style=\"color: #6A9955\"># If a path contributes negatively, ignore it<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><span style=\"color: #C586C0\">if<\/span><span style=\"color: #D4D4D4\"> leftPathSum &lt; <\/span><span style=\"color: #B5CEA8\">0<\/span><span style=\"color: #D4D4D4\">:<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">            leftPathSum = <\/span><span style=\"color: #B5CEA8\">0<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><span style=\"color: #C586C0\">if<\/span><span style=\"color: #D4D4D4\"> rightPathSum &lt; <\/span><span style=\"color: #B5CEA8\">0<\/span><span style=\"color: #D4D4D4\">:<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">            rightPathSum = <\/span><span style=\"color: #B5CEA8\">0<\/span><\/span>\n<span class=\"line\"><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><span style=\"color: #6A9955\"># Update global maximum: best path that passes through this node<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><span style=\"color: #569CD6\">self<\/span><span style=\"color: #D4D4D4\">.maxi = <\/span><span style=\"color: #DCDCAA\">max<\/span><span style=\"color: #D4D4D4\">(<\/span><span style=\"color: #569CD6\">self<\/span><span style=\"color: #D4D4D4\">.maxi, leftPathSum + root.val + rightPathSum)<\/span><\/span>\n<span class=\"line\"><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><span style=\"color: #6A9955\"># Return best single-branch path sum to parent<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><span style=\"color: #C586C0\">return<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #DCDCAA\">max<\/span><span style=\"color: #D4D4D4\">(leftPathSum, rightPathSum) + root.val<\/span><\/span>\n<span class=\"line\"><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">    <\/span><span style=\"color: #569CD6\">def<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #DCDCAA\">maxPathSum<\/span><span style=\"color: #D4D4D4\">(<\/span><span style=\"color: #9CDCFE\">self<\/span><span style=\"color: #D4D4D4\">, <\/span><span style=\"color: #9CDCFE\">root<\/span><span style=\"color: #D4D4D4\">: Optional[TreeNode]) -&gt; <\/span><span style=\"color: #4EC9B0\">int<\/span><span style=\"color: #D4D4D4\">:<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><span style=\"color: #569CD6\">self<\/span><span style=\"color: #D4D4D4\">.findMaxPathSum(root)<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><span style=\"color: #C586C0\">return<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #569CD6\">self<\/span><span style=\"color: #D4D4D4\">.maxi<\/span><\/span><\/code><\/pre><\/div>\n\n\n\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n\n\n\n<h2 class=\"wp-block-heading\">Code Explanation<\/h2>\n\n\n\n<ol class=\"wp-block-list\">\n<li><strong>Global variable <code>maxi<\/code>:<\/strong> Keeps track of the maximum path sum found so far. Initialized to negative infinity to handle trees with all negative values.<\/li>\n\n\n\n<li><strong>Recursive function <code>findMaxPathSum(root)<\/code>:<\/strong>\n<ul class=\"wp-block-list\">\n<li>Base case: If the node is <code>None<\/code>, return 0.<\/li>\n\n\n\n<li>Recursive calls: Compute path sums from left and right children.<\/li>\n\n\n\n<li>Negative pruning: If either path sum is negative, set it to 0 (ignore that side).<\/li>\n\n\n\n<li>Update <code>maxi<\/code>: Check if the current path <code>left + node + right<\/code> is greater than the previous best.<\/li>\n\n\n\n<li>Return upward: Pass only one branch (<code>node + max(left, right)<\/code>) to the parent, because you cannot pass both sides upward.<\/li>\n<\/ul>\n<\/li>\n\n\n\n<li><strong>Main function <code>maxPathSum(root)<\/code>:<\/strong>\n<ul class=\"wp-block-list\">\n<li>Calls the helper function on the root.<\/li>\n\n\n\n<li>Returns the global maximum path sum found.<\/li>\n<\/ul>\n<\/li>\n<\/ol>\n\n\n\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n\n\n\n<h2 class=\"wp-block-heading\">Time and Space Complexity<\/h2>\n\n\n\n<ul class=\"wp-block-list\">\n<li><strong>Time Complexity:<\/strong><br>Each node is visited once, and at each node we do constant work.<br>So time complexity is <strong>O(N)<\/strong>, where <code>N<\/code> is the number of nodes.<\/li>\n\n\n\n<li><strong>Space Complexity:<\/strong><br>The recursion stack depth is equal to the height of the tree.\n<ul class=\"wp-block-list\">\n<li>For a balanced tree: <code>O(log N)<\/code>.<\/li>\n\n\n\n<li>For a skewed tree: <code>O(N)<\/code>.<\/li>\n<\/ul>\n<\/li>\n<\/ul>\n\n\n\n<p>So worst-case space complexity is <strong>O(N)<\/strong>.<\/p>\n\n\n\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n\n\n\n<h2 class=\"wp-block-heading\">Dry Run Example<\/h2>\n\n\n\n<p>Consider <code>[-10, 9, 20, null, null, 15, 7]<\/code>:<\/p>\n\n\n\n<div class=\"wp-block-kevinbatdorf-code-block-pro cbp-has-line-numbers\" data-code-block-pro-font-family=\"Code-Pro-JetBrains-Mono\" style=\"font-size:.875rem;font-family:Code-Pro-JetBrains-Mono,ui-monospace,SFMono-Regular,Menlo,Monaco,Consolas,monospace;--cbp-line-number-color:#D4D4D4;--cbp-line-number-width:calc(1 * 0.6 * .875rem);line-height:1.5rem;--cbp-tab-width:2;tab-size:var(--cbp-tab-width, 2)\"><span style=\"display:block;padding:16px 0 0 16px;margin-bottom:-1px;width:100%;text-align:left;background-color:#1E1E1E\"><svg xmlns=\"http:\/\/www.w3.org\/2000\/svg\" width=\"54\" height=\"14\" viewBox=\"0 0 54 14\"><g fill=\"none\" fill-rule=\"evenodd\" transform=\"translate(1 1)\"><circle cx=\"6\" cy=\"6\" r=\"6\" fill=\"#FF5F56\" stroke=\"#E0443E\" stroke-width=\".5\"><\/circle><circle cx=\"26\" cy=\"6\" r=\"6\" fill=\"#FFBD2E\" stroke=\"#DEA123\" stroke-width=\".5\"><\/circle><circle cx=\"46\" cy=\"6\" r=\"6\" fill=\"#27C93F\" stroke=\"#1AAB29\" stroke-width=\".5\"><\/circle><\/g><\/svg><\/span><span role=\"button\" tabindex=\"0\" data-code=\"        -10\n        \/  \\\n       9    20\n           \/  \\\n          15   7\" style=\"color:#D4D4D4;display:none\" aria-label=\"Copy\" class=\"code-block-pro-copy-button\"><svg xmlns=\"http:\/\/www.w3.org\/2000\/svg\" style=\"width:24px;height:24px\" fill=\"none\" viewBox=\"0 0 24 24\" stroke=\"currentColor\" stroke-width=\"2\"><path class=\"with-check\" stroke-linecap=\"round\" stroke-linejoin=\"round\" d=\"M9 5H7a2 2 0 00-2 2v12a2 2 0 002 2h10a2 2 0 002-2V7a2 2 0 00-2-2h-2M9 5a2 2 0 002 2h2a2 2 0 002-2M9 5a2 2 0 012-2h2a2 2 0 012 2m-6 9l2 2 4-4\"><\/path><path class=\"without-check\" stroke-linecap=\"round\" stroke-linejoin=\"round\" d=\"M9 5H7a2 2 0 00-2 2v12a2 2 0 002 2h10a2 2 0 002-2V7a2 2 0 00-2-2h-2M9 5a2 2 0 002 2h2a2 2 0 002-2M9 5a2 2 0 012-2h2a2 2 0 012 2\"><\/path><\/svg><\/span><pre class=\"shiki dark-plus\" style=\"background-color: #1E1E1E\" tabindex=\"0\"><code><span class=\"line\"><span style=\"color: #D4D4D4\">        -<\/span><span style=\"color: #B5CEA8\">10<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        \/  \\<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">       <\/span><span style=\"color: #B5CEA8\">9<\/span><span style=\"color: #D4D4D4\">    <\/span><span style=\"color: #B5CEA8\">20<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">           \/  \\<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">          <\/span><span style=\"color: #B5CEA8\">15<\/span><span style=\"color: #D4D4D4\">   <\/span><span style=\"color: #B5CEA8\">7<\/span><\/span><\/code><\/pre><\/div>\n\n\n\n<ul class=\"wp-block-list\">\n<li>Start at <code>15<\/code>: left = 0, right = 0, current = 15 \u2192 update maxi = 15. Return 15.<\/li>\n\n\n\n<li>At <code>7<\/code>: left = 0, right = 0, current = 7 \u2192 maxi = 15 (still). Return 7.<\/li>\n\n\n\n<li>At <code>20<\/code>: left = 15, right = 7 \u2192 current path = 15 + 20 + 7 = 42 \u2192 update maxi = 42. Return <code>20 + max(15, 7) = 35<\/code>.<\/li>\n\n\n\n<li>At <code>9<\/code>: left = 0, right = 0, current = 9 \u2192 maxi still 42. Return 9.<\/li>\n\n\n\n<li>At <code>-10<\/code>: left = 9, right = 35 \u2192 current path = 9 + (-10) + 35 = 34 \u2192 maxi remains 42. Return upward <code>-10 + max(9, 35) = 25<\/code>.<\/li>\n<\/ul>\n\n\n\n<p>Final answer: <strong>42<\/strong>.<\/p>\n\n\n\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n\n\n\n<h2 class=\"wp-block-heading\">Conclusion<\/h2>\n\n\n\n<p>The <strong>Binary Tree Maximum Path Sum<\/strong> problem requires tracking two types of values at each node:<\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>The <strong>best complete path through the node<\/strong> (both sides + node value).<\/li>\n\n\n\n<li>The <strong>best path to return upward<\/strong> (one side + node value).<\/li>\n<\/ul>\n\n\n\n<p>By pruning negative sums and maintaining a global maximum, we achieve an efficient <strong>O(N)<\/strong> solution.<\/p>\n\n\n\n<p>This is a classic tree DP problem and an excellent example of combining local recursion with a global state to solve a complex optimization problem.<\/p>\n\n\n\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n\n\n\n<div class=\"wp-block-buttons is-content-justification-center is-layout-flex wp-container-core-buttons-is-layout-16018d1d wp-block-buttons-is-layout-flex\">\n<div class=\"wp-block-button\"><a class=\"wp-block-button__link wp-element-button\" href=\"https:\/\/codeanddebug.in\/course\/zero-to-hero-python-dsa\" target=\"_blank\" rel=\"noreferrer noopener\">Join our Advance DSA COURSE<\/a><\/div>\n<\/div>\n\n\n\n<p><em>For any changes to the article, kindly email at <a href=\"mailto:code@codeanddebug.in\" target=\"_blank\" rel=\"noreferrer noopener\">code@codeanddebug.in<\/a> or contact us at <a href=\"tel:+91-9712928220\" target=\"_blank\" rel=\"noreferrer noopener\">+91-9712928220<\/a>.<\/em><\/p>\n","protected":false},"excerpt":{"rendered":"<p>You are given the root of a binary tree. Your task is to find the maximum path sum in the tree. The path sum is the sum of the node values along that path.We want to maximize this path sum. Here&#8217;s the [Problem Link] to begin with. Examples Example 1 Example 2 Intuition and Approach<\/p>\n","protected":false},"author":1,"featured_media":1026,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[3,5],"tags":[14,18],"class_list":{"0":"post-1025","1":"post","2":"type-post","3":"status-publish","4":"format-standard","5":"has-post-thumbnail","7":"category-data-structures-and-algorithm","8":"category-expert","9":"tag-binary-trees","10":"tag-hard"},"featured_image_src":"https:\/\/codeanddebug.in\/blog\/wp-content\/uploads\/2025\/09\/binary-tree-maximum-path-sum-featured-image.png","author_info":{"display_name":"codeanddebug","author_link":"https:\/\/codeanddebug.in\/blog\/author\/codeanddebug\/"},"_links":{"self":[{"href":"https:\/\/codeanddebug.in\/blog\/wp-json\/wp\/v2\/posts\/1025","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/codeanddebug.in\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/codeanddebug.in\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/codeanddebug.in\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/codeanddebug.in\/blog\/wp-json\/wp\/v2\/comments?post=1025"}],"version-history":[{"count":1,"href":"https:\/\/codeanddebug.in\/blog\/wp-json\/wp\/v2\/posts\/1025\/revisions"}],"predecessor-version":[{"id":1027,"href":"https:\/\/codeanddebug.in\/blog\/wp-json\/wp\/v2\/posts\/1025\/revisions\/1027"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/codeanddebug.in\/blog\/wp-json\/wp\/v2\/media\/1026"}],"wp:attachment":[{"href":"https:\/\/codeanddebug.in\/blog\/wp-json\/wp\/v2\/media?parent=1025"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/codeanddebug.in\/blog\/wp-json\/wp\/v2\/categories?post=1025"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/codeanddebug.in\/blog\/wp-json\/wp\/v2\/tags?post=1025"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}