1.7 Store number of nodes in left subtree

Given a binary tree, count the number of nodes in each node’s left subtree, and store it in the numNodesLeft field.

Input: TreeNodeLeft root

Output: int number of nodes in the left subtree

Solution:

1. What to expect from left/right subtrees?

number of nodes in the left subtree

number of nodes in the right subtree

2. What to do at current layer?

count leftTotal == 1)

3. What to report to parent?

1) +2) + 1

1 & 3 could be asking the same problem, 2 & 3 might not be asking the same.

(current layer value, not the return value to the parent)

public class TreeNodeLeft {
  public int key;
  public TreeNodeLeft left;
  public TreeNodeLeft right;
  public int numNodesLeft;
  public TreeNodeLeft(int key) {
    this.key = key;
  }
}


public void numNodesLeft(TreeNodeLeft root) {
  numNodes(root);
}

public int numNodes(TreeNodeLeft root) {
  if (root == null) { return 0; }
  int left = numNodes(root.left);	//1
  int right = numNodes(root.right);	//1
  root.numNodesLeft = left;		//2
  return left + right + 1;		//3
}