4

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;

Improve this question
15
  • 1
    @user3112926, while I totally agree with you sir, I am seeking algorithmic improvements. Commented Jan 22, 2017 at 19:49
  • 1
    I dont know why I cant see the function returning anything else but zero. Commented Jan 22, 2017 at 19:54
  • 1
    As a nice code improvement: Since you already check root for NULL you can omit the null checks on the other levels and simply call minSumPath with the NULLs that are in left or right. Commented Jan 22, 2017 at 19:55
  • 1
    Yes, but in the next recursion step root->left and root->right will be the new root which is again checked for NULL. Commented Jan 22, 2017 at 19:57
  • 1
    The question is interesting though. There must be some way to exploit the BST's structure. Commented Jan 22, 2017 at 20:09

1 Answer 1

Reset to default
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.

Improve this answer
Sign up to request clarification or add additional context in comments.

2 Comments

Thank you for your answer. Do you see some way in which we can exploit the BST property?
@user6490375 I suspect pruning not promising subtrees is the best you can do. BSTs don't necessarily minimize the result on a specific subtree. You can easily construct a tree that has the shortest path on the left subtree and one that has the shortest path on the right subtree. Those will probably defeat any attempt to exploit the fact that lower values are to the left or something like that.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.