number of leaves in a binary tree

Question

I am a beginner to binary trees and have been working my way through the algorithms book. I have learnt about the various traversal methods of BSTs (pre-order, post order etc).

Could someone please explain how one can traverse a BST to count the number of nodes that are leaves (no children) please?

Many thanks!

Answer 1

Use a recursive method:

• For a leaf return 1.
• For a non-leaf, return the sum of that method applied to its children.

Example in PHP:

class BST {
  public $left;  // The substree containing the smaller entries
  public $right; // The substree containing the larger entries
  public $data;  // The value that is stored in the node
}

function countLeafs(BST $b) {
  // Test whether children exist ...
  if ($b->left || $b->right) {
    // ... yes, the left or the right child exists. It's not a leaf.
    // Return the sum of calling countLeafs() on all children.
    return ($b->left  ? countLeafs($b->left)  : 0)
         + ($b->right ? countLeafs($b->right) : 0);
  } else {
    // ... no, it's a leaf
    return 1;
  }
}