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;
}
@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