Skip to main content

Calculate size of a tree

In the field of computer science and data structures, one of the fundamental tasks is to calculate the size of a binary tree. The size of a binary tree is defined as the total number of nodes present in the tree. In this post, we will discuss the problem of calculating the size of a binary tree using a recursive approach. We will provide a detailed explanation of the problem, present the algorithm to solve it.

Count number of nodes in binary tree

Problem Statement

The problem we are addressing is to calculate the size of a given binary tree. The size of a binary tree is defined as the total number of nodes present in the tree, including both internal nodes and leaf nodes.

Example

Consider the binary tree provided in the code:

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

The size of this binary tree is 7, as it contains 7 nodes.

Idea to Solve

The main idea behind solving this problem is to use recursion. We can calculate the size of a binary tree by recursively calculating the size of its left subtree, its right subtree, and then adding 1 to account for the current node. This is because the size of a binary tree can be calculated as the sum of the sizes of its left and right subtrees, plus 1 for the current node.

Algorithm

  1. If the current node is null, return 0 (base case).
  2. Otherwise, return the sum of the following:
    • Recursively calculate the size of the left subtree.
    • Recursively calculate the size of the right subtree.
    • Add 1 for the current node.

Pseudocode

function treeSize(node):
if node is null:
    return 0
return treeSize(node.left) + treeSize(node.right) + 1

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