Question:
Given a binary tree, get the total number of nodes in it.
Example:
Consider the image given below:
Form the image above,
The total number of nodes are 7.
Solution:
This problem can be solved by recursive traversal.
Assume if you have only one node, and no left and right node.
Now, you will do
= 1 + get_num_of_nodes(left) + get_num_of_nodes(right)
= 1 + 0 + 0
= 1
Suppose,
if you have left and right children as shown below:
= 1 + get_node(left) + get_node(right)
= 1 + 1 + 1
= 3
We apply similar logic to all the nodes.
return 1 + get_num_of_nodes(left) + get_num_of_nodes(right);
We call “get_num_of_nodes” recursively for left and right nodes, and arrive at the solution.
Solution in C++
#include <iostream> using namespace std; // structure to hold binary tree node struct Node { int data; Node *left, *right; Node(int data) { this->data = data; this->left = this->right = nullptr; } }; int get_num_of_nodes(Node *root) { // Base case if (root == NULL) return 0; return 1 + get_num_of_nodes(root->left) + get_num_of_nodes(root->right); } int main() { Node* root = nullptr; /* Binary tree: 16 / \ / \ 10 25 / \ / \ / \ / \ 7 15 18 30 */ root = new Node(16); root->left = new Node(10); root->right = new Node(25); root->left->left = new Node(7); root->left->right = new Node(15); root->right->left = new Node(18); root->right->right = new Node(30); cout<<"Solution = " << get_num_of_nodes(root)<<endl; return 0; }
Output:
Solution = 7
Ritika
Wow!! Thanks for making this wonderful tutorial.
Please make a list of graph and dp interview questions too.