Nodes In Complete Binary Tree

Moderate
0/80
Average time to solve is 15m
profile
Contributed by
29 upvotes
Asked in companies
OracleMicrosoftArcesium

Problem statement

You are given the root of a complete binary tree, you need to calculate the number of nodes in the given complete binary tree.

A complete binary tree is a tree in which all the levels are completely filled except the last level. Nodes in the last level are as left as possible.

For Example:

In the above complete binary tree, all the levels are filled except for the last. In the last level, all the nodes in the last level are as far left as possible.
Detailed explanation ( Input/output format, Notes, Images )
Input Format:
The first line contains an Integer 'T' which denotes the number of test cases or queries to be run. Then the test cases follow.

The first line of each test case contains elements of the tree in the level order form. The line consists of values of nodes separated by a single space. In case a node is null, we take -1 in its place.

For example, the input for the tree depicted in the above image would be:

1
2 3
4 -1 5 6
-1 7 -1 -1 -1 -1
-1 -1

Explanation:

Level 1 :
The root node of the tree is 1.

Level 2 :
Left child of 1 = 2
Right child of 1 = 3

Level 3 :
Left child of 2 = 4
Right child of 2 = null (-1)
Left child of 3 = 5
Right child of 3 = 6

Level 4 :
Left child of 4 = null (-1)
Right child of 4 = 7
Left child of 5 = null (-1)
Right child of 5 = null (-1)
Left child of 6 = null (-1)
Right child of 6 = null (-1)

Level 5 :
Left child of 7 = null (-1)
Right child of 7 = null (-1)
Note:
The above format was just to provide clarity on how the input is formed for a given tree. 

The sequence will be put together in a single line separated by a single space. Hence, for the above-depicted tree, the input will be given as:

1 2 3 4 -1 5 6 -1 7 -1 -1 -1 -1 -1 -1
Output Format:
Return the number of nodes of the given complete 
binary tree.

Constraints:

1 <= T <= 10
0 <= Number of nodes in tree <= 10^5
1 <= Nodes Value <= 5*10^5

Time Limit: 1 second
Sample Input 1:
1
1 2 3 4 5 7 6 -1 -1 -1 -1 -1 -1 -1 -1
Sample Output 1:
7
Explanation For Sample Input 1:
For the above test case, the given tree is:

Level 1 :
The root node of the tree is 1

Level 2 :
Left child of 1 = 2
Right child of 1 = 3

Level 3 :
Left child of 2 = 4
Right child of 2 = 5
Left child of 3 = 7
Right child of 3 = 6

Level 4 :
Left child of 4 = null (-1)
Right child of 4 = null(-1)
Left child of 5 = null (-1)
Right child of 5 = null (-1)
Left child of 7 = null (-1)
Right child of 7 = null (-1).
Left child of 6 = null (-1)
Right child of 6 = null (-1)

Hence the total number of nodes in the given tree is 7.
Sample Input 2:
1
5 6 7 10 -1 -1 -1 -1 -1
Sample Output 2:
4
Hint

Traverse all the nodes of the tree.

Approaches (2)
Brute Force

Explanation:

 

The key idea is to traverse all the nodes of the tree and return the count of the number of nodes traversed.

 

Algorithm:

 

  • First, check whether the root is null or not. If the root is null then return 0 (since the given tree is empty).
  • Call recursion on the left subtree and right subtree. It will return the number of nodes in the left subtree and right subtree. Now return answer from left subtree + answer from right subtree + 1 (including the root node also).
Time Complexity

O(N), Where ‘N’ is the number of nodes in the binary tree.

 

We traverse all the nodes. Hence time complexity will be O(N).

Space Complexity

O(log(N)), Where ‘N’ is the number of nodes in the binary tree.

 

The space required for the recursion call stack will be equal to the height of the complete binary tree which is equal to log(N).

Code Solution
(100% EXP penalty)
Nodes In Complete Binary Tree
All tags
Sort by
Search icon

Interview problems

can anyone tell me where is failed my code

#include <bits/stdc++.h>
/*************************************************************

Following is the Binary Tree node structure


class BinaryTreeNode {
public :
T data;
BinaryTreeNode<T> *left;
BinaryTreeNode<T> *right;


BinaryTreeNode(T data) {
this -> data = data;
left = NULL;
right = NULL;
}
};


*************************************************************/


int countNodes(BinaryTreeNode<int> *root) {
if(!root)return 0;
return 1+countNodes(root->left)+countNodes(root->right);
}
110 views
2 replies
0 upvotes

Interview problems

Java straightforward solution

import java.util.* ;
import java.io.*; 
/*************************************************************
 
    Following is the Binary Tree node structure

    class BinaryTreeNode<T> {
        public T data;
        public BinaryTreeNode<T> *left;
        public BinaryTreeNode<T> *right;

        BinaryTreeNode(T data) {
            this.data = data;
            left = NULL;
            right = NULL;
        }
    };

*************************************************************/

public class Solution {
    public static int countNodes(BinaryTreeNode<Integer> root) {
        // Write your code here.
        Queue<BinaryTreeNode<Integer>> q = new LinkedList<>();
        q.add(root);
        int i = 1;
        while(!q.isEmpty()){
            BinaryTreeNode node = q.poll();

            if(node.left == null && node.right == null){
                continue;
            }
            if(node.left != null){
                q.add(node.left);
                i++;
            }
            if(node.right != null){
                q.add(node.right);
                i++;
            }
        }
        return i;
      }
}
45 views
0 replies
0 upvotes

Interview problems

C++ || Easy solution

#include <bits/stdc++.h> 

 

int height(BinaryTreeNode<int> *root, bool l){

 

    int h = 0;

 

    while(root){

 

        h++;

        if(l) root = root->left;

        else root = root->right;

 

    }

 

    return h;

 

}

 

int countNodes(BinaryTreeNode<int> *root) {

 

    int leftH = height(root, true);

    int rightH = height(root, false);

    if(leftH == rightH) return ((1 << leftH) - 1);

    

    return 1 + countNodes(root->left) + countNodes(root->right);

 

}

331 views
0 replies
1 upvote

Interview problems

TLE

can someone let me know why does this cause TLE??

 

#include <bits/stdc++.h> 
/*************************************************************
 
    Following is the Binary Tree node structure

    class BinaryTreeNode {
    public : 
        T data;
        BinaryTreeNode<T> *left;
        BinaryTreeNode<T> *right;

        BinaryTreeNode(T data) {
            this -> data = data;
            left = NULL;
            right = NULL;
        }
    };

*************************************************************/

int countNodes(BinaryTreeNode<int> *root) {
  queue<BinaryTreeNode<int>*>q;
  if(root==NULL) return 0;
  q.push(root);
  int ans=0;

  while(!q.empty()){
      auto it=q.front();
      ans++;
      q.pop();
      if(it->left) q.push(it->left);
      if(it->right) q.push(it->right);

  }

  return ans;
}
133 views
1 reply
0 upvotes

Interview problems

C++ Solution

int findLeftHeight(BinaryTreeNode<int>* root)

{

    int h=0;

    while(root)

    {

        h++;

        root=root->left;

    }

    return h;

}

int findRightHeight(BinaryTreeNode<int>* root)

{

    int h=0;

    while(root)

    {

        h++;

        root=root->right;

    }

    return h;

}

int countNodes(BinaryTreeNode<int> *root) {

  // Write your code here.

    if(!root)

        return 0;

    int lh=findLeftHeight(root);

    int rh=findRightHeight(root);

    if(lh==rh)

        return ((1<<lh)-1);

    return 1+countNodes(root->left)+countNodes(root->right);

}

691 views
0 replies
0 upvotes

Interview problems

EASY JAVA SOLUTION

import java.util.* ;

public class Solution {  public static int nodes(BinaryTreeNode<Integer> root){    if(root == null) return 0;    int left=nodes(root.left);    int right=nodes(root.right);    return 1+right+left;  }  public static int countNodes(BinaryTreeNode<Integer> root) {   int cnt=nodes(root);   return cnt;  } }

java

100 views
0 replies
0 upvotes

Interview problems

best solution in c++

#include <bits/stdc++.h> 

/*************************************************************

 

    Following is the Binary Tree node structure

 

    class BinaryTreeNode {

    public : 

        T data;

        BinaryTreeNode<T> *left;

        BinaryTreeNode<T> *right;

 

        BinaryTreeNode(T data) {

            this -> data = data;

            left = NULL;

            right = NULL;

        }

    };

 

*************************************************************/

int findlefthight(BinaryTreeNode<int>* node){

    int hight = 0;

    while(node){

        hight++;

        node = node->left;

    }

    return hight;

}

 

int findrightheight(BinaryTreeNode<int>* node){

    int hight = 0;

    while(node){

        hight++;

        node = node->right;

    }

    return hight;

}

int countNodes(BinaryTreeNode<int> *root) {

  // Write your code here.

  if(root == NULL)

  return 0;

 

  int lh = findlefthight(root);

  int rh = findrightheight(root);

 

  if(lh == rh) return (1<<lh)-1 ;

 

  int leftNodes = countNodes(root->left);

  int rightNodes = countNodes(root->right);

        

        return 1 + leftNodes + rightNodes;

}

391 views
0 replies
0 upvotes

Interview problems

c++ easiest

int height(BinaryTreeNode<int>*r,bool l)
{
    int c=0;
       while(r)
       {
       c++;
       if(l) r=r->left;
       else r=r->right;
       }
    return c;
}
int countNodes(BinaryTreeNode<int>*r) {
  if(r==NULL)return 0;
  int lh=height(r,true);
  int rh=height(r,false);
  
  if(lh==rh)return pow(2,lh)-1;
  return 1+countNodes(r->left)+countNodes(r->right);
}
252 views
0 replies
0 upvotes

Interview problems

Easy C++ Code With log(N) time complexity

#include <bits/stdc++.h> 

/*************************************************************

 

    Following is the Binary Tree node structure

 

    class BinaryTreeNode {

    public : 

        T data;

        BinaryTreeNode<T> *left;

        BinaryTreeNode<T> *right;

 

        BinaryTreeNode(T data) {

            this -> data = data;

            left = NULL;

            right = NULL;

        }

    };

 

*************************************************************/

int leftheight(BinaryTreeNode<int>* node){

        int h=0;

        while(node){

           h++;

           node=node->left;

        }

        return h;

    }

    int rightheight(BinaryTreeNode<int>* node){

      int h=0;

        while(node){

           h++;

           node=node->right;

        }

        return h;

    }

 

int countNodes(BinaryTreeNode<int> *root) {

  // Write your code here.

  if(root == NULL){

            return 0;

        }

    int lh= leftheight(root);

    int rh= rightheight(root);

    if(lh == rh){

        return (pow(2,lh)-1);

    }

    return 1+countNodes(root->left)+countNodes(root->right);

}

542 views
0 replies
0 upvotes

Interview problems

Discussion thread on Interview Problem | Nodes In Complete Binary Tree

Hey everyone, creating this thread to discuss the interview problem - Nodes In Complete Binary Tree.

 

Practise this interview question on Coding Ninjas Studio (hyperlinked with the following link): Nodes In Complete Binary Tree

 

293 views
2 replies
0 upvotes
Full screen
Console