Write a method named numEmpty that returns the number of empty (null) branches in a tree.
Your method accepts as its parameter a TreeNode referring to the root of the tree.
An empty (null) tree is considered to have one empty branch: the tree itself.
For non-empty trees, your method(s) should count the total number of empty branches among the nodes of the tree.
A leaf node has two empty branches.
A node with one non-empty child has one empty branch.
A node with two non-empty children (a full branch) has no empty branches.
For example, the tree below has 15 empty branches:
the right children of nodes 2, 4, 7;
the left children of 6, 8;
and both children of 9, 11, 12, 13, and 14.
So if a variable named tree refers to this tree's root, the call of numEmpty(tree) should return 15.
(1 (2 (4 (7 (11)))) (3 (5 (8 / (12)) (9)) (6 / (10 (13) (14)))))
Assume that you are interacting with TreeNodes as defined below:
public class TreeNode {
public int data;
public TreeNode left;
public TreeNode right;
public TreeNode() { ... }
public TreeNode(int data) { ... }
public TreeNode(int data, TreeNode left, TreeNode right) { ... }
}
