Algorithmic improvement for finding minimum sum in

问题:

I wrote the following function to find out the minimum sum of any path in a Binary Search Tree:

int minSumPath(TreeNode* root) {
    if(root==NULL)
        return 0;

    int sum = root->value;
    if(root->left!=NULL && root->right!=NULL)
        sum += min(minSumPath(root->left),minSumPath(root->right));
    else
        if(root->left==NULL)
            sum += minSumPath(root->right);
        else
            sum += minSumPath(root->left);

    return sum;
}

While the above code generates the correct output, I feel that I am not leveraging the fact that it is a Binary Search Tree (BST) and not just a Binary Tree.

In a BST the left child node is smaller than the root and right node, so logically we can only consider the left child nodes of each root; but what if the BST has only a single child on the right (with say value 10) and multiple child nodes on the left (with sum >10)?

In this case the minimum sum would be 10 (which is on the right).

How I would be able to leverage the BST property, if at all? Also, any other optimizations that I can use in my approach?

Note: Edited the code to resolve the error;

回答1:

An informed search could help in some cases.
In the worst case, the computational cost is exactly the same of your algorithm.

As an example:

int minSumPathOpt(TreeNode* root) {
    if(root == nullptr) return 0;

    int sum = -1;

    std::stack<std::pair<TreeNode*, int>> todo;
    todo.push(std::make_pair(root, 0));

    while(not todo.empty()) {
        std::pair<TreeNode*, int> curr = todo.top();
        todo.pop();

        TreeNode *node = curr.first;        
        int part = curr.second + node->value;

        if(sum == -1 || part < sum) {
            if(!node->left && !node->right) {
                sum = part;
            } else  {
                if(node->right) todo.push(std::make_pair(node->right, part));
                if(node->left) todo.push(std::make_pair(node->left, part));
            }
        }
    }

    return sum;
}

The basic idea is to track the current minimum while performing a DFS. This will give you the chance to prune entire subtrees whenever the sum of the values to their root are already greater than the current minimum.
Moreover, exploring the left tree before to look at the right one could help maximizing the result (no assurance indeed, but it's a good idea because of how BSTs are defined).

See a comparison of the two approaches on wandbox.
As you can see, the second function doesn't explore at all trees that are not promising.