Size of a tree is the number of elements present in the tree. Size of the below tree is 5.
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); |
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.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!