Skip to main content

Count internal nodes in binary tree

In the realm of binary trees and data structures, understanding the count of internal nodes is a crucial task. Internal nodes are nodes within a binary tree that have at least one child, either on the left or the right. This article will delve into the problem of counting internal 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 internal nodes in binary tree

Problem Statement

The problem at hand is to calculate the total number of internal nodes in a given binary tree. An internal node is a node within the tree that has at least one child node.

Example

 
      9
    /   \
   7     2
  /     / \
 5     6   3
        \
         4

The total number of internal nodes in this binary tree is 4.

Which is [7,9,2,6].

Idea to Solve

The central idea behind solving this problem is to use recursion. We can count the internal nodes in a binary tree by recursively calculating the internal nodes in its left subtree and right subtree, and then adding 1 if the current node is an internal node (i.e., it has at least one child).

Algorithm

  1. If the current node is null, return 0 (base case).
  2. Recursively calculate the number of internal nodes in the left subtree.
  3. Recursively calculate the number of internal nodes in the right subtree.
  4. If the current node has at least one child (either left or right), return the sum of internal nodes from the left and right subtrees, plus 1 for the current node.
  5. Otherwise, return the sum of internal nodes from the left and right subtrees.

Pseudocode

function countInternalNodes(node):
    if node is null:
        return 0
    leftInternalNodes = countInternalNodes(node.left)
    rightInternalNodes = countInternalNodes(node.right)
    if node.left is not null or node.right is not null:
        return leftInternalNodes + rightInternalNodes + 1
    else:
        return leftInternalNodes + rightInternalNodes

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