Write a program to Calculate Size of a tree | Recursion

Last Updated : 08 Oct, 2023

Size of a tree is the number of elements present in the tree. Size of the below tree is 5.

Example Tree

Size() function recursively calculates the size of a tree. It works as follows:
Size of a tree = Size of left subtree + 1 + Size of right subtree.

Algorithm:

size(tree)
1. If tree is empty then return 0
2. Else
     (a) Get the size of left subtree recursively  i.e., call 
          size( tree->left-subtree)
     (a) Get the size of right subtree recursively  i.e., call 
          size( tree->right-subtree)
     (c) Calculate size of the tree as following:
            tree_size  =  size(left-subtree) + size(right-
                               subtree) + 1
     (d) Return tree_size

C++

// A recursive C++ program to 
// calculate the size of the tree
#include <bits/stdc++.h>
using namespace std;
 
/* A binary tree node has data, pointer to left child 
and a pointer to right child */
class node 
{ 
    public:
    int data; 
    node* left; 
    node* right; 
}; 
 
/* Helper function that allocates a new node with the 
given data and NULL left and right pointers. */
node* newNode(int data) 
{ 
    node* Node = new node();
    Node->data = data; 
    Node->left = NULL; 
    Node->right = NULL; 
         
    return(Node); 
} 
 
/* Computes the number of nodes in a tree. */
int size(node* node) 
{ 
    if (node == NULL) 
        return 0; 
    else
        return(size(node->left) + 1 + size(node->right)); 
} 
 
/* Driver code*/
int main() 
{ 
    node *root = newNode(1); 
    root->left = newNode(2); 
    root->right = newNode(3); 
    root->left->left = newNode(4); 
    root->left->right = newNode(5); 
     
    cout << "Size of the tree is " << size(root); 
    return 0; 
} 
 
// This code is contributed by rathbhupendra

C

#include <stdio.h>
#include <stdlib.h>
 
/* A binary tree node has data, pointer to left child 
   and a pointer to right child */
struct node 
{
    int data;
    struct node* left;
    struct node* right;
};
 
/* Helper function that allocates a new node with the
   given data and NULL left and right pointers. */
struct node* newNode(int data) 
{
  struct node* node = (struct node*)
                       malloc(sizeof(struct node));
  node->data = data;
  node->left = NULL;
  node->right = NULL;
   
  return(node);
}
 
/* Computes the number of nodes in a tree. */
int size(struct node* node) 
{  
  if (node==NULL) 
    return 0;
  else    
    return(size(node->left) + 1 + size(node->right));  
}
 
/* Driver program to test size function*/   
int main()
{
  struct node *root = newNode(1);
  root->left        = newNode(2);
  root->right       = newNode(3);
  root->left->left  = newNode(4);
  root->left->right = newNode(5);   
 
  printf("Size of the tree is %d", size(root));  
  getchar();
  return 0;
}

Java

// A recursive Java program to calculate the size of the
// tree
 
/* Class containing left and right child of current
   node and key value*/
class Node {
    int data;
    Node left, right;
 
    public Node(int item)
    {
        data = item;
        left = right = null;
    }
}
 
/* Class to find size of Binary Tree */
class BinaryTree {
    Node root;
 
    // Function to return the size of binary tree
    int size() { return size(root); }
 
    /* computes number of nodes in tree */
    int size(Node node)
    {
        if (node == null)
            return 0;
        else
            return (size(node.left) + 1 + size(node.right));
    }
 
    public static void main(String args[])
    {
        /* creating a binary tree and entering the nodes */
        BinaryTree tree = new BinaryTree();
        tree.root = new Node(1);
        tree.root.left = new Node(2);
        tree.root.right = new Node(3);
        tree.root.left.left = new Node(4);
        tree.root.left.right = new Node(5);
 
        System.out.println("The size of binary tree is : "
                           + tree.size());
    }
}

Python3

# Python Program to find the size of binary tree
 
# A binary tree node
class Node:
 
    # Constructor to create a new node
    def __init__(self, data):
        self.data = data 
        self.left = None
        self.right = None
 
# Computes the number of nodes in tree
def size(node):
    if node is None:
        return 0
    else:
        return (size(node.left)+ 1 + size(node.right))
 
 
# Driver program to test above function
root = Node(1)
root.left = Node(2)
root.right = Node(3)
root.left.left  = Node(4)
root.left.right = Node(5)
 
print("Size of the tree is %d" %(size(root)))
 
# This code is contributed by Nikhil Kumar Singh(nickzuck_007)

C#

using System;
 
// A recursive C# program to calculate the size of the tree 
 
/* Class containing left and right child of current 
   node and key value*/
public class Node
{
    public int data;
    public Node left, right;
 
    public Node(int item)
    {
        data = item;
        left = right = null;
    }
}
 
/* Class to find size of Binary Tree */
public class BinaryTree
{
    public Node root;
 
    /* Given a binary tree. Print its nodes in level order 
       using array for implementing queue */
    public virtual int size()
    {
        return size(root);
    }
 
    /* computes number of nodes in tree */
    public virtual int size(Node node)
    {
        if (node == null)
        {
            return 0;
        }
        else
        {
            return (size(node.left) + 1 + size(node.right));
        }
    }
 
    public static void Main(string[] args)
    {
        /* creating a binary tree and entering the nodes */
        BinaryTree tree = new BinaryTree();
        tree.root = new Node(1);
        tree.root.left = new Node(2);
        tree.root.right = new Node(3);
        tree.root.left.left = new Node(4);
        tree.root.left.right = new Node(5);
 
        Console.WriteLine("The size of binary tree is : " + tree.size());
    }
}
 
  //  This code is contributed by Shrikant13

Javascript

<script>
 
      // A recursive JavaScript program to
      // calculate the size of the tree
 
      /* Class containing left and right child of current
         node and key value*/
      class Node {
        constructor(item) {
          this.data = item;
          this.left = null;
          this.right = null;
        }
      }
 
      /* Class to find size of Binary Tree */
      class BinaryTree {
        constructor() {
          this.root = null;
        }
        /* computes number of nodes in tree */
        size(node = this.root) {
          if (node == null) {
            return 0;
          } else {
            return this.size(node.left) + 1 + this.size(node.right);
          }
        }
      }
      /* creating a binary tree and entering the nodes */
      var tree = new BinaryTree();
      tree.root = new Node(1);
      tree.root.left = new Node(2);
      tree.root.right = new Node(3);
      tree.root.left.left = new Node(4);
      tree.root.left.right = new Node(5);
 
      document.write("Size of the tree is " + tree.size() + "<br>");
       
</script>

Output:

Size of the tree is 5

Time Complexity: O(N)

As every node is visited once.

Auxiliary Space: O(N)

The extra space is due to the recursion call stack and the worst case occurs when the tree is either left skewed or right skewed.

Since this program is similar to traversal of tree, time and space complexities will be same as Tree traversal (Please see our Tree Traversal post for details)

Using Morris Traversal:

The basic idea of Morris traversal is to use the empty right child of a node to store a temporary link to the next node in the inorder traversal. By using this link, we can traverse the binary tree without using any extra space for a stack or recursion.

Follow the steps to solve the problem:

Initialize a counter variable to 0 and a current pointer to the root of the binary tree.
While the current pointer is not NULL:
a. If the current node has no left child, increment the counter and move the current pointer to its right child.
b. Otherwise, find the rightmost node in the left subtree of the current node.
i. If this node does not have a right child, set its right child to the current node and move the current pointer to its left child.
ii. Otherwise, the right child of this node already points to the current node, so we have visited all the nodes in the left subtree of the current node. Set the right child of this node to NULL, increment the counter, and move the current pointer to its right child.
When the current pointer becomes NULL, we have visited all the nodes in the binary tree. Return the counter variable.

Below is the implementation of the above approach:

C++

// C++ code to implement morris traversal approach
#include <iostream>
using namespace std;
 
// Definition for a binary tree node
struct Node {
    int val;
    Node* left;
    Node* right;
    Node(int x) : val(x), left(NULL), right(NULL) {}
};
 
// function to count the number of nodes in a binary tree using Morris traversal
int countNodes(Node* root) {
    int count = 0;
    Node* current = root;
    while (current != NULL) {
        // if the current node has no left child, increment the count and move to the right child
        if (current->left == NULL) {
            count++;
            current = current->right;
        }
        else {
            // find the rightmost node in the left subtree of the current node
            Node* predecessor = current->left;
            while (predecessor->right != NULL && predecessor->right != current) {
                predecessor = predecessor->right;
            }
            if (predecessor->right == NULL) {
                // set the right child of the rightmost node to the current node
                predecessor->right = current;
                // move to the left child of the current node
                current = current->left;
            }
            else {
                // restore the right child of the rightmost node to NULL
                predecessor->right = NULL;
                // increment the count for the current node
                count++;
                // move to the right child of the current node
                current = current->right;
            }
        }
    }
    // return the count of nodes in the binary tree
    return count;
}
// Driver Code
int main() {
    // create binary tree
    Node* root = new Node(1);
    root->left = new Node(10);
    root->right = new Node(39);
    root->left->left = new Node(5);
 
    // count nodes using Morris traversal
    int nodeCount = countNodes(root);
 
    // print the result
    cout << "The size of binary tree is: " << nodeCount << endl;
 
    return 0;
}
// This code is contributed by Veerendra_Singh_Rajpoot

Java

// Java code to implement morris traversal approach
class Node {
    int val;
    Node left, right;
 
    Node(int x) {
        val = x;
        left = right = null;
    }
}
 
class MorrisTraversal {
 
    // function to count the number of nodes in a binary tree 
  // using Morris traversal
    public static int countNodes(Node root) {
        int count = 0;
        Node current = root;
        while (current != null) {
            // if the current node has no left child, 
          // increment the count and move to the right child
            if (current.left == null) {
                count++;
                current = current.right;
            } else {
                // find the rightmost node in the left subtree of 
              // the current node
                Node predecessor = current.left;
                while (predecessor.right != null && predecessor.right != current) {
                    predecessor = predecessor.right;
                }
                if (predecessor.right == null) {
                    // set the right child of the rightmost node to 
                  // the current node
                    predecessor.right = current;
                    // move to the left child of the current node
                    current = current.left;
                } else {
                    // restore the right child of the rightmost node 
                  // to NULL
                    predecessor.right = null;
                    // increment the count for the current node
                    count++;
                    // move to the right child of the current node
                    current = current.right;
                }
            }
        }
        // return the count of nodes in the binary tree
        return count;
    }
 
    // Driver Code
    public static void main(String[] args) {
        // create binary tree
        Node root = new Node(1);
        root.left = new Node(10);
        root.right = new Node(39);
        root.left.left = new Node(5);
 
        // count nodes using Morris traversal
        int nodeCount = countNodes(root);
 
        // print the result
        System.out.println("The size of binary tree is: " + nodeCount);
    }
}
// This code is contributed by phasing17

Python

# Definition for a binary tree node
class Node:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None
 
# function to count the number of nodes in a binary tree using Morris traversal
def countNodes(root):
    count = 0
    current = root
    while current is not None:
        # if the current node has no left child, increment the count and move to the right child
        if current.left is None:
            count += 1
            current = current.right
        else:
            # find the rightmost node in the left subtree of the current node
            predecessor = current.left
            while predecessor.right is not None and predecessor.right != current:
                predecessor = predecessor.right
            if predecessor.right is None:
                # set the right child of the rightmost node to the current node
                predecessor.right = current
                # move to the left child of the current node
                current = current.left
            else:
                # restore the right child of the rightmost node to None
                predecessor.right = None
                # increment the count for the current node
                count += 1
                # move to the right child of the current node
                current = current.right
    # return the count of nodes in the binary tree
    return count
 
# Driver Code
if __name__ == "__main__":
    # create binary tree
    root = Node(1)
    root.left = Node(10)
    root.right = Node(39)
    root.left.left = Node(5)
 
    # count nodes using Morris traversal
    nodeCount = countNodes(root)
 
    # print the result
    print("The size of binary tree is:", nodeCount)
#this code is contributed by Veerendra_Singh_Rajpoot

C#

using System;
 
// Definition for a binary tree node
class Node
{
    public int val;
    public Node left;
    public Node right;  
    public Node(int x)
    {
        val = x;
        left = null;
        right = null;
    }
}
class GFG
{
    // Function to count the number of nodes in binary tree 
  // using Morris traversal
    public static int CountNodes(Node root)
    {
        int count = 0;
        Node current = root;      
        while (current != null)
        {
            // If the current node has no left child
          // increment the count and move to the right child
            if (current.left == null)
            {
                count++;
                current = current.right;
            }
            else
            {
                // Find the rightmost node in the left subtree of current node
                Node predecessor = current.left;             
                while (predecessor.right != null && predecessor.right != current)
                {
                    predecessor = predecessor.right;
                }            
                if (predecessor.right == null)
                {
                    // Set the right child of the rightmost node to current node
                    predecessor.right = current;
                    // Move to the left child of the current node
                    current = current.left;
                }
                else
                {
                    // Restore the right child of the rightmost node to null
                    predecessor.right = null;
                    // Increment the count for the current node
                    count++;
                    // Move to the right child of the current node
                    current = current.right;
                }
            }
        }      
        // Return the count of nodes in the binary tree
        return count;
    }
    // Driver Code
    static void Main(string[] args)
    {
        // Create binary tree
        Node root = new Node(1);
        root.left = new Node(10);
        root.right = new Node(39);
        root.left.left = new Node(5);
        // Count nodes using Morris traversal
        int nodeCount = CountNodes(root);
        // Print the result
        Console.WriteLine("The size of the binary tree is: " + nodeCount);
    }
}

Javascript

// Definition for a binary tree node
class TreeNode {
    constructor(val) {
        this.val = val;
        this.left = null;
        this.right = null;
    }
}
 
// Function to count the number of nodes in a binary tree using Morris traversal
function countNodes(root) {
    let count = 0;
    let current = root;
 
    while (current !== null) {
        // If the current node has no left child, 
        // increment the count and move to the right child
        if (current.left === null) {
            count++;
            current = current.right;
        } else {
            // Find the rightmost node in the left subtree of the current node
            let predecessor = current.left;
            while (predecessor.right !== null && predecessor.right !== current) {
                predecessor = predecessor.right;
            }
            if (predecessor.right === null) {
                // Set the right child of the rightmost node to the current node
                predecessor.right = current;
                // Move to the left child of the current node
                current = current.left;
            } else {
                // Restore the right child of the rightmost node to null
                predecessor.right = null;
                // Increment the count for the current node
                count++;
                // Move to the right child of the current node
                current = current.right;
            }
        }
    }
 
    // Return the count of nodes in the binary tree
    return count;
}
// Create a binary tree
const root = new TreeNode(1);
root.left = new TreeNode(10);
root.right = new TreeNode(39);
root.left.left = new TreeNode(5);
// Count nodes using Morris traversal
const nodeCount = countNodes(root);
// Print the result
console.log("The size of binary tree is: " + nodeCount);

Output

The size of binary tree is: 4

Time Complexity: O(N) , since traversing all the nodes in the tree only once.

Auxiliary Space: O(1) , No extra space is required.

GeeksforGeeks

Improve

Previous Article

Succinct Encoding of Binary Tree

Diameter of a Binary Tree

Similar Reads

Why is Tail Recursion optimization faster than normal Recursion?

What is tail recursion? Tail recursion is defined as a recursive function in which the recursive call is the last statement that is executed by the function. So basically nothing is left to execute after the recursion call. What is non-tail recursion? Non-tail or head recursion is defined as a recursive function in which the recursive call is the f

Program to calculate value of nCr using Recursion

Given two numbers N and r, find the value of NCr using recursion Examples: Input: N = 5, r = 2Output: 10Explanation: The value of 5C2 is 10 Input: N = 3, r = 1Output: 3 Approach 1: One very interesting way to find the C(n,r) is the recursive method which is based on the recursive equation. C(n,r) = C(n-1,r-1) + C(n-1,r) Below is the implementation

Program to Calculate e^x by Recursion ( using Taylor Series )

The value of the Exponential function can be calculated using Taylor Series. [Tex]e^x[/Tex] = 1 + x/1! + [Tex]x^2[/Tex]/2! + [Tex]x^3[/Tex]/3! + ...... + until n termsAs the number of terms increases the more precise value of ex is obtained. To find e^x using the recursive function, we need to use static variables. A function can return only one va

Iterative program to Calculate Size of a tree

Size of a tree is the number of elements present in the tree. Size of the below tree is 5. Recommended: Please solve it on "PRACTICE" first, before moving on to the solution. Approach The idea is to use Level Order Traversing 1) Create an empty queue q 2) temp_node = root /*start from root*/ 3) Loop while temp_node is not NULL a) Enqueue temp_node’

Write program to calculate pow(x, n)

Given two integers x and n, write a function to compute xn. We may assume that x and n are small and overflow doesn't happen. Examples : Input : x = 2, n = 3Output : 8 Input : x = 7, n = 2Output : 49 Recommended PracticeOdd GameTry It!Naive Approach: To solve the problem follow the below idea: A simple solution to calculate pow(x, n) would multipl

Tail recursion to calculate sum of array elements.

Given an array A[], we need to find the sum of its elements using Tail Recursion Method. We generally want to achieve tail recursion (a recursive function where recursive call is the last thing that function does) so that compilers can optimize the code. Basically, if recursive call is the last statement, the compiler does not need to save the stat

Write a program to Delete a Tree

To delete a tree, we must traverse all the nodes of the tree and delete them one by one. So, which traversal we should use - inorder traversal, preorder traversal, or the postorder traversal? The answer is simple. We should use the postorder traversal because before deleting the parent node, we should delete its child nodes first.We can delete the

The Great Tree-List Recursion Problem.

Asked by Varun Bhatia. Question: Write a recursive function treeToList(Node root) that takes an ordered binary tree and rearranges the internal pointers to make a circular doubly linked list out of the tree nodes. The”previous” pointers should be stored in the “small” field and the “next” pointers should be stored in the “large” field. The list sho

Inorder Tree Traversal without recursion and without stack!

Using Morris Traversal, we can traverse the tree without using stack and recursion. The idea of Morris Traversal is based on Threaded Binary Tree. In this traversal, we first create links to Inorder successor and print the data using these links, and finally revert the changes to restore original tree. 1. Initialize current as root 2. While current

Print ancestors of a given binary tree node without recursion

Given a Binary Tree and a key, write a function that prints all the ancestors of the key in the given binary tree.For example, consider the following Binary Tree 1 / \ 2 3 / \ / \ 4 5 6 7 / \ / 8 9 10 Following are different input keys and their ancestors in the above tree Input Key List of Ancestors ------------------------- 1 2 1 3 1 4 2 1 5 2 1

Article Tags :

Practice Tags :

Tree