Write a method countLeftNodes that returns the number of left children in the tree. A left child is a node that appears as the root of the left-hand subtree of another node. An empty tree has 0 left nodes. For example, the following tree has four left children (the nodes storing the values 5, 1, 4, and 7):

 +---+ | 3 | +---+ / \ +---+ +---+ | 5 | | 2 | +---+ +---+ / / \ +---+ +---+ +---+ | 1 | | 4 | | 6 | +---+ +---+ +---+ / +---+ | 7 | +---+ 

Assume that you are adding this method to the IntTree class as defined below:

import java.util.*;

public class IntTree { private IntTreeNode overallRoot;

// pre : max > 0 // post: constructs a sequential tree with given number of // nodes public IntTree(int max) { if (max <= 0) { throw new IllegalArgumentException("max: " + max); } overallRoot = buildTree(1, max); } public IntTree() { overallRoot = null; } // constructor added so we can build page 1029 reference trees public IntTree(IntTreeNode given) { overallRoot = given; }

// post: returns a sequential tree with n as its root unless // n is greater than max, in which case it returns an // empty tree private IntTreeNode buildTree(int n, int max) { if (n > max) { return null; } else { return new IntTreeNode(n, buildTree(2 * n, max), buildTree(2 * n + 1, max)); } }

// post: prints the tree contents using a preorder traversal public void printPreorder() { System.out.print("preorder:"); printPreorder(overallRoot); System.out.println(); }

// post: prints the tree contents using a preorder traversal // post: prints in preorder the tree with given root private void printPreorder(IntTreeNode root) { if (root != null) { System.out.print(" " + root.data); printPreorder(root.left); printPreorder(root.right); } }

// post: prints the tree contents using a inorder traversal public void printInorder() { System.out.print("inorder:"); printInorder(overallRoot); System.out.println(); }

// post: prints in inorder the tree with given root private void printInorder(IntTreeNode root) { if (root != null) { printInorder(root.left); System.out.print(" " + root.data); printInorder(root.right); } }

// post: prints the tree contents using a post order traversal public void printPostorder() { System.out.print("postorder:"); printPostorder(overallRoot); System.out.println(); }

// post: prints in postorder the tree with given root private void printPostorder(IntTreeNode root) { if (root != null) { printPostorder(root.left); printPostorder(root.right); System.out.print(" " + root.data); } }

// post: prints the tree contents, one per line, following an // inorder traversal and using indentation to indicate // node depth; prints right to left so that it looks // correct when the output is rotated. public void printSideways() { printSideways(overallRoot, 0); }

// post: prints in reversed preorder the tree with given // root, indenting each line to the given level private void printSideways(IntTreeNode root, int level) { if (root != null) { printSideways(root.right, level + 1); for (int i = 0; i < level; i++) { System.out.print(" "); } System.out.println(root.data); printSideways(root.left, level + 1); } }

}