// Given a binary tree, find a minimum path sum from root to a leaf.
//
// For example, the minimum path in this tree is[10, 5, 1, -1], which has sum 15.
//
// 10
// / \
// 5 5
// \ \
// 2 1
// /
//-1
#include <iostream>
#include <string>
#include <vector>
#include <stack>
#include <algorithm>
using namespace std;
class Node
{
public:
Node(int val)
{
data = val;
}
int data;
Node* right;
Node* left;
};
void LeafPathRecurs(Node* node, int *minSum, int currSum, Node** targetNode)
{
if (node == nullptr)
return;
currSum = currSum + node->data;
// check for leaf node
if (node->left == nullptr && node->right == nullptr)
{
if (currSum < *minSum)
{
*minSum = currSum;
*targetNode = node;
}
}
LeafPathRecurs(node->left, minSum, currSum, targetNode);
LeafPathRecurs(node->right, minSum, currSum, targetNode);
}
bool getPath(Node* root, Node* target_leaf)
{
if (root == nullptr)
return false;
if (root == target_leaf ||
getPath(root->left, target_leaf) ||
getPath(root->right, target_leaf))
{
printf("%d ", root->data);
return true;
}
return false;
}
int MinLeafPath(Node* root)
{
Node* targetNode;
int minSum = INT_MAX;
LeafPathRecurs(root, &minSum, 0 ,&targetNode);
getPath(root, targetNode);
return minSum;
}
Node* generateTree()
{
Node* root = new Node(10);
Node* n1 = new Node(5);
root->left = n1;
Node* n2 = new Node(5);
root->right = n2;
Node* n3 = new Node(1);
n2->right = n3;
Node* n4 = new Node(2);
n1->right = n4;
Node* n5 = new Node(-1);
n4->left = n5;
return root;
}
int main()
{
Node* root = generateTree();
auto result = MinLeafPath(root);
return 0;
}
Comments