public class exercises
{
  public static void printTree(TreeNode root)
  {
    if(root == null)
      return;
    System.out.print(root.getValue() + " ");
    printTree(root.getLeft());
    printTree(root.getRight());
  }
  public static boolean isLeaf(TreeNode node)
  {
    return node != null && node.getLeft() == null 
           && node.getRight() == null;
  }
  public static int sumTree(TreeNode root)
  {
    if(root == null)
      return 0;
    return ((Integer)root.getValue()).intValue()
           + sumTree(root.getLeft())
           + sumTree(root.getRight());
  }
  public static int countPaths(TreeNode root)
  {
    if(root == null)
      return 0;
    int sum = 0;
    if(root.getLeft() != null)
      sum += 1 + countPaths(root.getLeft());
    if(root.getRight() != null)
      sum += 1 + countPaths(root.getRight());
    return sum;
  }
  public static int depth(TreeNode root)
  {
    if(root == null)
      return 0;
    return Math.max(1 + depth(root.getLeft()),
                    1 + depth(root.getRight()));
  }
  public static int countNodes(TreeNode root)
  {
    if(root == null)
      return 0;
    return 1 + countNodes(root.getLeft()) + 
           countNodes(root.getRight());
  }
  public static double bushRatio(TreeNode root)
  {
    if(root == null)
      return 0.;
    return countNodes(root) / 
           (Math.pow(2., depth(root)) - 1.);
  }
  public static TreeNode copy(TreeNode root)
  {
    if(root == null)
      return null;
    return new TreeNode(root.getValue(), 
                        copy(root.getLeft()),
                        copy(root.getRight()));
  }
  public static TreeNode mirrorImage(TreeNode root)
  {
    if(root == null)
      return null;
    return new TreeNode(root.getValue(), 
                        mirrorImage(root.getRight()),
                        mirrorImage(root.getLeft()));
  }
  public static boolean sameShape(TreeNode root1, 
                                  TreeNode root2)
  {
    if(root1 == null && root2 == null)
      return true;
    if((root1 == null && root2 != null) ||
       (root1 != null && root2 == null))
      return false;
    return sameShape(root1.getLeft(), root2.getLeft()) &&
           sameShape(root1.getRight(), root2.getRight());
  }
  public static boolean hasSameSubtree(TreeNode root1, 
                                       TreeNode root2)
  {
    if(root2 == null)
      return true;
    if(root1 == null)
      return false;
    if(sameShape(root1,root2))
      return true;
    return sameShape(root1.getLeft(),root2) || 
           sameShape(root1.getRight(),root2); 
  }
  public static void main()
  {
    TreeNode n6 = new TreeNode(6),
             n5 = new TreeNode(5),
             n4 = new TreeNode(4),
             n3 = new TreeNode(3, n6, null),
             n2 = new TreeNode(2, n4, n5),
             n1 = new TreeNode(1, n2, n3);
    printTree(n1);
    System.out.println("\nisLeaf(n5) = " + isLeaf(n5));
    System.out.println("isLeaf(n1) = " + isLeaf(n1));
    System.out.println("sumTree(n1) = " + sumTree(n1));
    System.out.println("countPaths(n1) = " + countPaths(n1));
    System.out.println("depth(n1) = " + depth(n1));
    System.out.println("countNodes(n1) = " + countNodes(n1));
    System.out.println("bushRatio(n1) = " + bushRatio(n1));
    System.out.print("copy(n1) = ");
    printTree(copy(n1));
    System.out.print("\nmirrorImage(n1) = ");
    printTree(mirrorImage(n1));
    System.out.println("\nsameShape(n1, n1) = " + sameShape(n1, n1));
    System.out.println("sameShape(n2, n3) = " + sameShape(n2, n3));
    System.out.println("hasSameSubtree(n1, n2) = " + hasSameSubtree(n1, n2));
    System.out.println("hasSameSubtree(n2, n3) = " + hasSameSubtree(n2, n3));
  }
}