Skip to content

Instantly share code, notes, and snippets.

@fanzhang312
Last active August 30, 2020 04:45
Show Gist options
  • Save fanzhang312/a3491f19c0a67303a5b1 to your computer and use it in GitHub Desktop.
Save fanzhang312/a3491f19c0a67303a5b1 to your computer and use it in GitHub Desktop.
Find the minimum path sum for binary tree (From root to leaf)
// Find the minimum path sum (from root to leaf)
public static int minPathSum(TreeNode root) {
if(root == null) return 0;
int sum = root.val;
int leftSum = minPathSum(root.left);
int rightSum = minPathSum(root.right);
if(leftSum < rightSum){
sum += leftSum;
}else{
sum += rightSum;
}
return sum;
}
@liewsanmin
Copy link

what about
10
5 15
1
???

@swapnala
Copy link

swapnala commented Feb 6, 2017

There should be a slight change in this code. This code will not handle a node where there only left/right node exists
Eg:
image

Assuming 7 - 3- 1 -0 is the shortest path here it will return an answer of 10 instead of 11.
The modified code is below:

public static int minPathSum(TreeNode root) {
        if(root == null) return 0;
        int sum = root.val;
        int leftSum = Integer.MAX_VALUE;
        int rightSum = Integer.MAX_VALUE;
        if(root.right==null && root.left==null) {
            return sum;
        }else{

            if(root.left!=null){
                leftSum = minPathSum(root.left);
            }
            if (root.right!=null){
                rightSum = minPathSum(root.right);
            }
            if(leftSum < rightSum){
                sum += leftSum;
            }else{
                sum += rightSum;
            }
        }

        return sum;
    }

@absognety
Copy link

@swapnala, thanks
Please find the python implementation of the same.

import math
class Node(object):
    def __init__(self,data):
        self.data = data
        self.left = None
        self.right = None
        
root = Node(10)
root.left = Node(5)
root.left.right = Node(2)
root.right = Node(5)
root.right.right = Node(1)
root.right.right.left = Node(-1)

def min_sum(root):
    if root == None:
        return 0
    result = root.data
    leftresult = math.inf
    rightresult = math.inf
    if (root.left == None) and (root.right == None):
        return result
    else:
        if (root.left != None):
            leftresult = min_sum(root.left)
        if (root.right != None):
            rightresult = min_sum(root.right)
        if (leftresult < rightresult):
            result += leftresult
        else:
            result += rightresult
    return result

print (min_sum(root))

root = Node(7)
root.left = Node(3)
root.right = Node(10)
root.left.left = Node(1)
root.left.left.left = Node(0)
root.right.left = Node(8)

print (min_sum(root))

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment