Skip to main content

Count leaf nodes in binary tree

In the realm of binary trees and data structures, one of the important tasks is to count the number of leaf nodes in a binary tree. Leaf nodes are nodes in the tree that do not have any children. In this post, we'll delve into the problem of counting leaf nodes in a binary tree using a recursive approach. We will provide a comprehensive explanation of the problem, outline the approach to solve it.

Total leaf nodes in binary tree

Problem Statement

The problem at hand is to count the total number of leaf nodes in a given binary tree. A leaf node is defined as a node that does not have any left or right children.

Example

Consider the binary tree provided in the code:


      9
    /   \
   7     2
  /     / \
 5     6   3
      / \  / \
     1   4 8  10

The total number of leaf nodes in this binary tree is 5.

Idea to Solve

The fundamental idea behind solving this problem is to use recursion. We can count the leaf nodes of a binary tree by recursively calculating the leaf nodes in its left subtree and right subtree, and then adding 1 if the current node is a leaf node (i.e., it has no children).

Algorithm

  1. If the current node is null, return 0 (base case).
  2. Recursively calculate the number of leaf nodes in the left subtree.
  3. Recursively calculate the number of leaf nodes in the right subtree.
  4. If the current node has no left or right child, return 1 (as it's a leaf node).
  5. Otherwise, return the sum of leaf nodes from the left and right subtrees.

Pseudocode

function countLeafNodes(node):
    if node is null:
        return 0
    leftLeafNodes = countLeafNodes(node.left)
    rightLeafNodes = countLeafNodes(node.right)
    if node.left is null and node.right is null:
        return leftLeafNodes + rightLeafNodes + 1
    else:
        return leftLeafNodes + rightLeafNodes

Code Solution

Time Complexity

The time complexity of the algorithm is O(n), where n is the number of nodes in the binary tree. This is because each node is visited exactly once in the recursive traversal.





Comment

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.

New Comment