Please login

Prime

Prepinsta Prime

Video courses for company/skill based Preparation

(Check all courses)
Get Prime Video
Prime

Prepinsta Prime

Purchase mock tests for company/skill building

(Check all mocks)
Get Prime mock
PrepInsta
Feed
Prime

Find Size Of Binary Tree In C++

January 22, 2021

Size Of Binary Tree

Size of Binary tree is defined as the number of nodes in the given tree. It can be easily calculated using recursion and tree traversals. In this article this problem is solved using recursion.

Calculating the size of binary tree in C++

Algorithm:

  1. If node is empty, return NULL.
  2. Otherwise, recursively call the size function for the left and right subtree.
  3. Return 1 + sum of left and right subtree.

 

Calculating the size of binary tree using recursion in C++

Code:

#include<bits/stdc++.h> 
using namespace std; 
class Tree {
    public:
        int data;
        Tree* left = NULL,*right = NULL;
        // Constructor initialised
        Tree(int x) {
            data = x;
            left = NULL;
            right = NULL;
        }
};
int size_tree(Tree *root) {
    if (root == NULL) return 0; // If null return 0
    // Recursively Call for left subtree and right subtree
    return 1 + size_tree(root -> right) + size_tree(root -> left);
}
int main() {
    Tree *root = new Tree(10);
    root -> left = new Tree(22);
    root -> right = new Tree(10);
    root -> left -> left = new Tree(11);
    root -> left -> right = new Tree(10);
    cout << size_tree(root);
    return 0;
}

Output:

5

Time Complexity To Find Size Of Binary Tree

Time Complexity

O(n)

Space Complexity

O(1)