CODEWITHSUNDEEP
javabinary-tree
noMAD
noMAD

Reputation: 7844

Path to leaf which has particular sum in binary tree

I know how to find if a binary tree has a certain path with a given sum (If this is not the best way please let me know):

int pathSum(MyNode root, int sum)
{
    if(root == null)
        return -1;
    int temp = sum - root.value;
    return(pathSum(root.left,temp) || pathSum(root.right,temp));
}

What I am not able to figure out is how to print the particular path.

My Node class looks like this:

class MyNode {
    int value;
    MyNode left;
    MyNode right;

    MyNode(int value)
    {
        this.value = value;
    }
}

Upvotes: 3

Views: 1777

Answers (4)

kasavbere
kasavbere

Reputation: 6003

Try this, use overloading:

 public void pathToSum(int sum) {
    pathToSum(root, sum);
}

private boolean pathToSum(Node n, int sum) {
    if (null != n) {
        sum -= n.data;
        boolean found = pathToSum(n.left, sum);

        if (!found) {
            found = pathtoSum(n.right, sum);
        }
        if (found) {
            println(n.data);
                            return found;
        }
    }
    return 0 == sum ? true : false;
}

This code is tested with the following classes:

import java.util.LinkedList;
import java.util.Queue;
public class BST {
Node root;
public BST(){
    root = null;
}

public void insert(int el){

    Node tmp = root, p=null;
    while(null!=tmp && el != tmp.data){
        p=tmp;
        if(el<tmp.data)
            tmp=tmp.left;
        else
            tmp=tmp.right;
    }
    if(tmp == null){
        if(null == p)
            root = new Node(el);
        else if(el <p.data)
            p.left= new Node(el);
        else
            p.right=new Node(el);
    }
}//

public void pathToSum(int sum) {
    pathToSum(root, sum);
}//

private boolean pathToSum(Node n, int sum) {
    if (null != n) {
        sum -= n.data;
        boolean found = pathToSum(n.left, sum);

        if (!found) {
            found = pathToSum(n.right, sum);
        }
        if (found) {
            System.out.println(n.data);
            return found;
        }
    }
    return 0 == sum ? true : false;
}

public static void main(String[] args){
    int[] input={50,25,75,10,35,60,100,5,20,30,45,55,70,90,102};
    BST bst = new BST();
    for(int i:input)
        bst.insert(i);
    bst.pathToSum(155);
}
}

class Node{
public int data;
public Node left;
public Node right;
public Node(int el){
    data = el;
}
}

Result:

45
35
25
50

Upvotes: 4

Adam
Adam

Reputation: 36703

Nice puzzle, I liked it. You almost had it, just some confusion over int vs boolean, and not checking end condition of sum being zero.

public class NodeSums {

    static boolean pathSum(MyNode root, int sum) {
        boolean ret;
        if (root == null) {
            ret = sum == 0;
        } else {
            int remain = sum - root.value;
            ret = pathSum(root.left,remain) || pathSum(root.right, remain);
        }
        return ret;
    }

    static class MyNode {
        int value;
        MyNode left;
        MyNode right;

        MyNode(int value) {
            this.value = value;
        }
    }

    public static void main(String[] args) {

        /**
         * Valid sums will be 3, 8, and 9
         * 
         *    1 -- 2 
         *      --
         *      -- 3 -- 4
         *           --
         *           -- 5
         */
        MyNode root = new MyNode(1);
        root.left = new MyNode(2);
        root.right = new MyNode(3);
        root.right.left = new MyNode(4);
        root.right.right = new MyNode(5);

        for (int i = 1; i < 10; i++) {
            System.out.println("Path sum " + i + " " + pathSum(root, i));
        }
    }
}

Output

Path sum 1 false
Path sum 2 false
Path sum 3 true
Path sum 4 false
Path sum 5 false
Path sum 6 false
Path sum 7 false
Path sum 8 true
Path sum 9 true

Upvotes: 1

Jakub Zaverka
Jakub Zaverka

Reputation: 8874

I suggest to alter your MyNode class to include a parent node:

MyNode left;
MyNode right;
MyNode parent;

MyNode(int value, MyNode parent)
{
    this.value = value;
    this.parent = parent;
}

and then when you hit a node with correct sum, you can pass that node to another function that goes throug the ancestry until it hits node with null parent (the root).

Upvotes: 1

fgb
fgb

Reputation: 18569

If you store the parent of each node in MyNode, you can find the (reversed) path from the root to any node by getting the parent in a loop until it is null.

Also, your code for pathSum seems to be mixing booleans and ints, and you never check the value of sum.

Upvotes: 0

Related Questions