// Name   :
// Matric#:
// Group# :
// CS1102 Lab 8C
//
// A copy of this program can also be found at:
// http://www.comp.nus.edu.sg/~cs1102/B/c.html
//
// TITLE: Count the number of paths in a binary tree with a given sum.
//  
// Consider a binary tree where each elements is an integer.  We define 
// a path in a binary tree as the sequence of nodes from the root to
// a leaf.  So, a tree with K number of leaves has K different paths.
// We also define path-sum as the sum of all elements along a path.
// 
// In this lab, you are to write a method that counts the number of 
// paths with a given path-sum.
//
// You are to complete the method pathCount(int n) for BinaryTree.  
// pathCount(n) returns the number of paths whose path-sum is n.  Your 
// implementation should not visit parts of the tree that are impossible 
// to produce the given path-sum.
//
// Important Remarks:
// - make sure you think, plan, and verify your solution before you begin 
//   coding.
// - think recursively!


/** 
 * A Node in a binary tree.  Each node has a integer element, and two
 * references to the left and right node.   Note that left, right and
 * element are not private.  Therefore, you can access their values
 * directly just like in the notes and textbook. (e.g., t.left)
 **/
class BinaryNode {
  int element; 
  BinaryNode left;
  BinaryNode right;
  
  public BinaryNode(int k) {
    element = k;
    left = right = null;
  }
}


/**
 * Binary Tree class.
 **/
class BinaryTree {
  BinaryNode root; //root of the tree

  public BinaryTree() 
  {
    root = null;  
  }


  /** 
   * prints out the tree for debugging.  Just a wrapper around
   * auxiliary method print(int level, BinaryNode t).
   */
  public void print() {
     print(0, root);
     System.out.println();
  }


  /** 
   * Returns the number of paths whose path-sum is n.  (i.e., the number of 
   * paths whose sum of all elements along the path is n).  You may want to 
   * define an auxiliary recursive method to help compute the pathCount.
   */
  public int pathCount(int n)
  {
    // WRITE YOUR CODE HERE.
    return 0; //just to compile, you may want to remove it.
  }


  /**
   * An auxiliary method that prints out the tree for debugging.
   */ 
  private void print(int depth, BinaryNode t) {
     System.out.println(t.element);
    
     if (t.left != null) {
         for (int i = 0; i <= depth; i++)  
             System.out.print(" ");
         print(depth + 1, t.left);
     }
     
     if (t.right != null) {
         for (int i = 0; i <= depth; i++)
             System.out.print(" ");
         print(depth + 1, t.right);
     }
  }
}

public class Lab8C {
  public static void main(String[] args) {
    BinaryTree t = new BinaryTree();
    t.root = new BinaryNode(6);
    t.root.left  = new BinaryNode(3);
    t.root.left.right  = new BinaryNode(5);
    t.root.left.left  = new BinaryNode(2);
    t.root.right = new BinaryNode(7);
    t.root.right.right = new BinaryNode(1);

    t.print();     //print the tree 

    int numOfPaths = t.pathCount(14); //test pathCount method.
    System.out.println("There are "+numOfPaths+
                         " path/s from root to leaf with sum equals to 14");
    numOfPaths = t.pathCount(12); //test pathCount method.
    System.out.println("There are "+numOfPaths+
                         " path/s from root to leaf with sum equals to 12");
    numOfPaths = t.pathCount(0); //test pathCount method.
    System.out.println("There are "+numOfPaths+
                         " path/s from root to leaf with sum equals to 0");
    numOfPaths = t.pathCount(-5); //test pathCount method.
    System.out.println("There are "+numOfPaths+
                         " path/s from root to leaf with sum equals to -5");
  }
}