Write a program to Calculate Size of a tree | Recursion

Last Updated : 25 Oct, 2024

Given a binary tree, the task is to find the size of the tree. The size of a tree is the number of nodes present in the tree.

Examples:

Input:

Output: 6
Explanation: The number of nodes in the above binary tree is 6.

Approach:

The idea is to recursively calculate the size of tree. For each node (starting from root node), calculate the size of left subtree and right subtree and return the size of current subtree (size of left subtree + size of right subtree + 1).

Below is the implementation of the above approach:

C++

// C++ program to find the size
// of a binary tree.
#include<bits/stdc++.h>
using namespace std;

class Node {
public:
    int data;
    Node *left, *right;
    Node(int x) {
        data = x;
        left = nullptr;
        right = nullptr;
    }
};

// Recursive function to find the 
// size of binary tree.
int getSize(Node* root) {
    if (root == nullptr)
        return 0;
    
    // Find the size of left and right 
    // subtree.
    int left = getSize(root->left);
    int right = getSize(root->right);
    
    // return the size of curr subtree.
    return left+right+1;
}

int main() {

    // Constructed binary tree is
    //         1
    //        / \
    //       2   3
    //      / \
    //     4   5
    Node* root = new Node(1);
    root->left = new Node(2);
    root->right = new Node(3);
    root->left->left = new Node(4);
    root->left->right = new Node(5);
    cout << getSize(root) << endl;

    return 0;
}

// C program to find the size
// of a binary tree.
#include <stdio.h>
#include <stdlib.h>

struct Node {
    int data;
    struct Node* left;
    struct Node* right;
};

// Recursive function to find the 
// size of binary tree.
int getSize(struct Node* root) {
    if (root == NULL)
        return 0;
    
    // Find the size of left and right 
    // subtree.
    int left = getSize(root->left);
    int right = getSize(root->right);
    
    // return the size of curr subtree.
    return left + right + 1;
}

struct Node* createNode(int x) {
    struct Node* newNode = 
    (struct Node*)malloc(sizeof(struct Node));
    newNode->data = x;
    newNode->left = NULL;
    newNode->right = NULL;
    return newNode;
}

int main() {

    // Constructed binary tree is
    //         1
    //        / \
    //       2   3
    //      / \
    //     4   5
    struct Node* root = createNode(1);
    root->left = createNode(2);
    root->right = createNode(3);
    root->left->left = createNode(4);
    root->left->right = createNode(5);

    printf("%d\n", getSize(root));

    return 0;
}

Java

// Java program to find the size
// of a binary tree.
import java.util.*;

class Node {
    int data;
    Node left, right;

    Node(int x) {
        data = x;
        left = null;
        right = null;
    }
}

class GfG {

    // Recursive function to find the 
    // size of binary tree.
    static int getSize(Node root) {
        if (root == null)
            return 0;

        // Find the size of left and right 
        // subtree.
        int left = getSize(root.left);
        int right = getSize(root.right);

        // return the size of curr subtree.
        return left + right + 1;
    }

    public static void main(String[] args) {

        // Constructed binary tree is
        //         1
        //        / \
        //       2   3
        //      / \
        //     4   5
        Node root = new Node(1);
        root.left = new Node(2);
        root.right = new Node(3);
        root.left.left = new Node(4);
        root.left.right = new Node(5);

        System.out.println(getSize(root));
    }
}

Python

# Python program to find the size
# of a binary tree.

class Node:
    def __init__(self, x):
        self.data = x
        self.left = None
        self.right = None

# Recursive function to find the 
# size of binary tree.
def getSize(root):
    if root is None:
        return 0

    # Find the size of left and right 
    # subtree.
    left = getSize(root.left)
    right = getSize(root.right)

    # return the size of curr subtree.
    return left + right + 1

if __name__ == "__main__":

    # Constructed binary tree is
    #         1
    #        / \
    #       2   3
    #      / \
    #     4   5
    root = Node(1)
    root.left = Node(2)
    root.right = Node(3)
    root.left.left = Node(4)
    root.left.right = Node(5)

    print(getSize(root))

// C# program to find the size
// of a binary tree.
using System;

class Node {
    public int data;
    public Node left, right;

    public Node(int x) {
        data = x;
        left = null;
        right = null;
    }
}

class GfG {

    // Recursive function to find the 
    // size of binary tree.
    static int GetSize(Node root) {
        if (root == null)
            return 0;

        // Find the size of left and right 
        // subtree.
        int left = GetSize(root.left);
        int right = GetSize(root.right);

        // return the size of curr subtree.
        return left + right + 1;
    }

    static void Main(string[] args) {

        // Constructed binary tree is
        //         1
        //        / \
        //       2   3
        //      / \
        //     4   5
        Node root = new Node(1);
        root.left = new Node(2);
        root.right = new Node(3);
        root.left.left = new Node(4);
        root.left.right = new Node(5);

        Console.WriteLine(GetSize(root));
    }
}

JavaScript

// JavaScript program to find the size
// of a binary tree.

class Node {
    constructor(x) {
        this.data = x;
        this.left = null;
        this.right = null;
    }
}

// Recursive function to find the 
// size of binary tree.
function getSize(root) {
    if (root === null)
        return 0;

    // Find the size of left and right 
    // subtree.
    let left = getSize(root.left);
    let right = getSize(root.right);

    // return the size of curr subtree.
    return left + right + 1;
}

// Constructed binary tree is
//         1
//        / \
//       2   3
//      / \
//     4   5
let root = new Node(1);
root.left = new Node(2);
root.right = new Node(3);
root.left.left = new Node(4);
root.left.right = new Node(5);

console.log(getSize(root));