CC-7 : : Check Binary Tree path sum.

Description:

Given an integer as input, check if sum of node data of any path of Tree Nodes from root of Binary Tree to a particular node is same as input integer.

Test cases and expected outputs:

Input Parameters	Expected outputs
Check path with sum: 48 Check path with sum: 49 Check path with sum: 87	48 Path sum Found? true 49 Path sum Found? false 87 Path sum Found? true

Pseudocode:

Method checkPathSum (root, SumToBeFound)

If node data of root is equal to sumToBeFound, and the root node has no children, return true.

Recursively call method checkPathSum() with left child of root as first argument and (sumTobeFound minus root.getNodeData()). If the recursively called method returns true, then return true from current method call also.

Recursively call method checkPathSum() with right child of root as first argument and (sumTobeFound minus root.getNodeData()). If the recursively called method returns true, then return true from current method call also.

If both above recursive calls return false, then return false from current method call also.

Code:

public boolean checkPathSum(BinTreeNode root, int sumToBeFound) throws Exception{
	if (root==null) {return false;}
	if ((root.getNodeData()==sumToBeFound) 
			&& (root.getLeftChild()==null) 
			&& (root.getRightChild()==null)) {
		return true;		
	}
	return checkPathSum(root.getLeftChild(),sumToBeFound-root.getNodeData())
			|| checkPathSum(root.getRightChild(),sumToBeFound-root.getNodeData());
}

Click here to download and run code and test cases !

Below fully running code can be copied and run on Eclipse or other Java IDEs. Refer the classname in code below. If the class name below is "A", save the code below to a file named A.java before running it. Be sure to try your own test cases to enhance your understanding ! You can also tweak the code to optimize or add enhancements and custom features.

Note: for easy reference BinTreeNode is included as internal class in program below. Ideally it should be in a separate file.

public class BinTreeCheckPathSum
{	

public boolean checkPathSum(BinTreeNode root, int sumToBeFound) throws Exception{
	if (root==null) {return false;}
	if ((root.getNodeData()==sumToBeFound) 
			&& (root.getLeftChild()==null) 
			&& (root.getRightChild()==null)) {
		return true;		
	}
	return checkPathSum(root.getLeftChild(),sumToBeFound-root.getNodeData())
			|| checkPathSum(root.getRightChild(),sumToBeFound-root.getNodeData());
}
 	
public static void main(String[] args) {
   /***********************
	Test cases given below:
    ***********************/
   boolean retVal=false;
	try {
	BinTreeCheckPathSum chk=new BinTreeCheckPathSum();
	BinTreeNode root=chk.new BinTreeNode(4);
	//Left L1 Children
	root.setLeftChild(chk.new BinTreeNode(5));
	root.setRightChild(chk.new BinTreeNode(7));
	
	//Left L2 Children
	root.getLeftChild().setLeftChild(chk.new BinTreeNode(6));
	root.getLeftChild().setRightChild(chk.new BinTreeNode(78));
	
	//Left L3 Children
	root.getLeftChild().getLeftChild().setLeftChild(chk.new BinTreeNode(33));
	
	//Right L2 Children
	root.getRightChild().setLeftChild(chk.new BinTreeNode(14));
	
	
	//Right L3 Children
	root.getRightChild().getLeftChild().setLeftChild(chk.new BinTreeNode(8));
	root.getRightChild().getLeftChild().setRightChild(chk.new BinTreeNode(16));
	
	//Right L3 Children
	root.getRightChild().getLeftChild().getRightChild().setLeftChild(chk.new BinTreeNode(18));
	
	//Right L4 Children
	root.getRightChild().getLeftChild().getRightChild().getLeftChild().setLeftChild(chk.new BinTreeNode(9));
	
	
	retVal=chk.checkPathSum(root, 48);
	System.out.println("48 Found? "+retVal);
	
	retVal=chk.checkPathSum(root, 49);
	System.out.println("49 Found? "+retVal);
	
	retVal=chk.checkPathSum(root, 87);
	System.out.println("87 Found? "+retVal);
	
	retVal=chk.checkPathSum(root, 33);
	System.out.println("33 Found? "+retVal);
	
	retVal=chk.checkPathSum(root, 68);
	System.out.println("68 Found? "+retVal);
	
	retVal=chk.checkPathSum(root, 69);
	System.out.println("69 Found? "+retVal);
	
	
	}catch (Exception exception) {
	System.out.print("Exception: "+ exception);
		exception.printStackTrace();
	}
	
}

public class BinTreeNode {
	private BinTreeNode leftNode=null;
	private BinTreeNode rightNode=null;
	private int nodeData=0;
	
	public BinTreeNode(int data) {
		nodeData=data;
	}	
	public BinTreeNode getLeftChild() {
		return leftNode;
	}
	public void setLeftChild(BinTreeNode leftNode) {
		this.leftNode = leftNode;
	}
	public BinTreeNode getRightChild() {
		return rightNode;
	}
	public void setRightChild(BinTreeNode rightNode) {
		this.rightNode = rightNode;
	}
	public int getNodeData() {
		return nodeData;
	}
	public void setNodeData(int nodeData) {
		this.nodeData = nodeData;
	}

}
	
}