Get minimum path sum of Root to leaf path in a tree

January 13, 2018

Introduction

It is my turn to write a tree recursive solution called minimum value of all path sum, for each path root to leaf node in a tree. I have already practiced multiple times, this time I spent first 15 minutes to write down my analysis.

Analysis of algorithm

It is the first time I have time to carefully go over each step and write down the analysis. This only happens after I master the recursive function using the template.

First of all I write down all the paths from root to leaf node first, and add the sum for each path. And I give a title called "Go over all the paths". Next I write down "Find minimum value". Third I write down my depth first search using recursive method. I write my template for recursive solution.

Here is my analysis of the algorithm:

	Problem statement:
	Find minimum sum for each path from root node to leaf node in a tree.
	0
	/ | \
	5 3 6
	/ /\ /\
	4 2 0 1 5
	/ /
	1 10
	\
	1
	Julia's analysis: January 13, 2018
	Go over all the paths
	0->5->4 9
	0->3->2->1->1 7
	0->3->0->10 13
	0->6->1 7
	0->6->5 11
	Find minimum value
	total 5 paths, not path itself, need minimum sales path -> Math.min(9, 7, 13, 7, 11) -> minimum 7
	DFS search:
	depth first search -> recursive
	Template:
	if the node is null
	return 0
	base case
	if there is no child
	return node.value
	// have multiple child
	minPath = Int.Max
	foreach child
	fidnMinPath
	update minPath
	return node.value + minPath
	recurrence formula
	Write code

view raw Analysis of sum from root to leaf node in a tree hosted with ❤ by GitHub

Code review

Here is my C# code.