Count Leaf Nodes 🌿

Welcome to the exciting world of Data Structures and Algorithms! In this lesson, we'll dive deep into understanding Leaf Nodes, a fundamental concept in trees. Let's get started!

Understanding Trees 🎲

Before we jump into leaf nodes, let's first understand what a tree is. A tree is a collection of nodes where each node has at most one parent, but any number of children. Trees are used extensively in Computer Science to represent hierarchical structures.

Defining Leaf Nodes 🍃

A Leaf Node (also known as a Leaf Vertex or Terminal Node) is a node in a tree with no children. These nodes don't have any branches to expand. In other words, if a node is not the root and doesn't have any subtrees, it's a leaf node.

📝 Note: Root nodes are special leaf nodes that have no parent.

Counting Leaf Nodes 📊

Now that we understand what leaf nodes are, let's learn how to count them. Counting leaf nodes is a common problem in graph theory and can be solved using Depth-First Search (DFS) algorithm.

Depth-First Search (DFS) 🕵️‍♂️

DFS is an algorithm for traversing or searching tree or graph structures. It explores as far as possible along each branch before backtracking.

Let's see how we can use DFS to count leaf nodes in a tree.

Pseudo Code

function countLeafNodes(root) {
  if root is null then return 0

  if root doesn't have children then return 1

  let count = 0
  for each child node do
    count += countLeafNodes(child)

  return count
}

💡 Pro Tip: In the above pseudo-code, we first check if the root is null (empty). If it is, we return 0. If the root has no children, we return 1 as it's a leaf node. If the root has children, we traverse each child recursively and add the count of its leaf nodes to our total count.

Practical Example 🔨

Let's count the leaf nodes in the following binary tree:

   A
  / \
 B   C
    / \
   D   E

We start at the root node A. Since it has children B and C, we don't count it as a leaf node yet.
We recursively traverse B and find that it has no children, so it's a leaf node (count = 1).
We recursively traverse C and find that it has a child D. We continue traversing D and find that it has a child E, but E is also a leaf node (count = 1).
Now we return to D, and since it has a child E, we don't count it as a leaf node yet.
We return to C, and since it has a child D which has a leaf node (E), we add 1 to our count (count = 2).
We return to A, and since it has children B and C (both of which have leaf nodes), we add their counts together (count = 1 + 2 = 3).

So, the total number of leaf nodes in this tree is 3.

Coding in Python 🐍

Let's write a Python function to count the leaf nodes in a binary tree.

python

class Node:
  def __init__(self, key):
    self.left = None
    self.right = None
    self.val = key

def countLeafNodes(root):
  if root is None:
    return 0

  if root.left is None and root.right is None:
    return 1

  return countLeafNodes(root.left) + countLeafNodes(root.right)

# Test the function
tree = Node(1)
tree.left = Node(2)
tree.right = Node(3)
tree.left.left = Node(4)
tree.left.right = Node(5)

print("Number of leaf nodes: ", countLeafNodes(tree))

In this code, we define a Node class to represent tree nodes. We then define a countLeafNodes function that uses the DFS approach we discussed earlier to count leaf nodes.

Quiz Time 🤓

That's all for this lesson on counting leaf nodes! With this understanding, you're well on your way to mastering Data Structures and Algorithms. Keep learning, and happy coding! 🚀🎉