Paths with sum k

Tags: , ,

In last post Paths in Binary Search Tree we discussed and solved problem to find all the paths in binary search tree. The next step is to find a specific path with a sum in a binary tree.
Given a number K, find all paths with sum K in Binary tree. For example, if K  = 21, and given below the binary tree, the path will be [10,5,6].

path with sum k in binary tree

Keep in mind, that there can be more than one path with a given sum. Confirm with the interviewer what does he expects in implementation.

Thoughts

We already know how to traverse all paths in the binary search tree. All we need now is to qualify those paths if all nodes in path sum up to given number K.

Let’s figure our recursive nature of the problem. At the root level, we are required to find a path with sum K. As soon as we add root in the path, remaining nodes in path need to add up to K – root.value, in either left or right subtree. For example, in the below tree,  at the whole tree level, the sum required is 21.

path with sum k

As we move down, that is root is added to the path, the sum required further is 11 from either left or right subtree. The problem is reduced to a subproblem.

paths with sum k

At this point, we cannot go forward with node(19), as the sum required will be reduced to negative. However, we can move down node(5) and the problem is reduced to finding a path with sum 6.

path with given sum

At this point, we have to find a path with sum 6 in the left and right subtree of node(5). On left subtree, add node(1) to the path. Now the problem reduces to finding a path with sum 5 on right and left subtree of node(1). However, there are not subtrees of nodes (1). Hence, path [ 10,5,1 ] is not correct path.

On the other hand, after adding node(6) in the path, the sum required is 0 and also node(6) is a leaf node, hence path [10,5,6] is required path with given sum in the binary search tree.

As we worked out example, we came up with some basic conditions for algorithm.

  1. If at any node in path, sum required becomes negative, do not go down the path.
  2. If sum required become zero, check if the last node added is leaf node. If yes, then add path to solution.
  3. If sum required is greater than zero, and node is leaf node, then that path is not with required sum.

Show me the paths with sum k implementation

package com.company.BST;

import java.util.ArrayList;

/**
 * Created by sangar on 10.5.18.
 */
public class BinarySearchTree {

 /*   public class Node {
        private int value;
        private  Node left;
        private Node right;

        public Node(int value) {
            this.value = value;
            this.left = null;
            this.right = null;
        }
    }
*/
  
    private void pathWithGivenPath(Node root, int sum, 
                   ArrayList<Integer> path, List<List<Integer> res){
        if(root == null)
            return;

        if(sum < 0) return;

        int subSum = sum - root.value;
        path.add(root.val);

        boolean isLeaf = ( root.left == null 
                       && root.right == null );
        if(isLeaf && subSum == 0){
            res.add(new ArrayList<>(path));
        }
        pathWithGivenPath(root.left, subSum, path);
        pathWithGivenPath(root.right, subSum, path);

        path.remove(path.size()-1);
    }

    public void printPathWithGivenPath(int sum){
        ArrayList<Node> path = new ArrayList<>();
        pathWithGivenPath(this.root, sum, path);
    }
}

The complexity of the algorithm to print all paths with a given sum in a binary search tree is O(n) as we will be scanning all nodes of BST at least once.

Please share if there is something wrong or missing. If you want to contribute and share your knowledge with thousands of learners across the world, please reach out to us at [email protected]