Write a method countEmpty that returns the number of empty branches in a tree. A

Question

Write a method countEmpty that returns the number of empty branches in a tree. An empty 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 (indicated by circles):

Explanation / Answer

public int numEmpty() { return numEmpty(myRoot); } simple java functio for the same. private int numEmpty(TreeNode node) { if (node == null) // base case return 1; else { int leftSubtree = numEmpty(node.left); int rightSubtree = numEmpty(node.right); return leftSubtree + rightSubtree; } }

Related Questions

Navigate

• Browse (All)
• Browse W
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.