int numberOfNodes(int N){
return pow(2,N-1);
}
Problem
Submissions
Hints & solutions
Discuss
Number Of Nodes
Easy
0/40
Contributed by
39 upvotes
Problem statement
Given an integer 'N', determine the maximum number of nodes present on 'Nth' level in a binary tree.
For Example:
N = 3
For level 1, we have 1 node.
For level 2, we have 2 nodes.
For level 3, we have 4 nodes
Output = 4, as level 3 has maximum 4 nodes.
Detailed explanation ( Input/output format, Notes, Images )
Input format:
The first line of each test case contains an integer ‘N’.
The output contains an integer denoting the maximum number of nodes present on 'N'th level in a binary tree.
You don’t need to print anything. Just implement the given function.
Sample Input 1:
2
Sample Output 1:
2
Explanation Of Sample Input 1:
N = 2
For level 1, we have 1 node.
For level 2, we have 2 nodes.
Output = 2, as level 2 has maximum 2 nodes.
Sample Input 2:
4
Sample Output 2:
8
Explanation Of Sample Input 2:
N = 4
For level 1, we have 1 node.
For level 2, we have 2 nodes.
For level 3, we have 4 nodes
For level 4, we have 8 nodes
Output = 8, as level 4 has maximum 8 nodes.
Constraints:
1 <= N <= 20
Time Limit: 1 sec
Hint
Hint 1
Deduce it mathematically.
Approaches (1)
Approach 1
Maths
Approach:
The approach calculates the maximum number of nodes on level ‘N’ of a binary tree using the formula 2^(N-1).
Algorithm:
- Initialise nodes = (1 << (N - 1))
- return nodes
Time Complexity
O(1)
All the operations performed are constant time operations, hence the time complexity is O(1).
Space Complexity
O(1)
No extra space is used. Hence, the space complexity is O(1).
Code Solution
(100% EXP penalty)
Number Of Nodes
All tags
Sort by
Interview problems
Number Of Nodes | Easy C++ solution O(1)
337 views
0 replies
2 upvotes
Interview problems
Java Solution
import java.util.*;
public class Solution {
public static int numberOfNodes(int N){
// Write your code here.
if(N==0){
return 0;
}
return (int)(Math.pow(2,N-1));
}
}
163 views
0 replies
0 upvotes
Interview problems
Java Solution
//One-Line Solution
public class Solution {
public static int numberOfNodes(int N){
return 1<<N-1;
}
}
//Another method Solution
public class Solution {
public static int numberOfNodes(int N){
if(N==0 || N==1){
return N;
}
int noOfNode=1;
for(int i=1;i<N;i++){
noOfNode=noOfNode+noOfNode;
}
return noOfNode;
}
}
140 views
0 replies
0 upvotes
Interview problems
Java one liner using bitwise operator
public class Solution {
public static int numberOfNodes(int N){
return 1<<N-1;
}
}
62 views
0 replies
0 upvotes
Interview problems
Number of Nodes
int numberOfNodes(int N){
if(N==0){
return 0;
}
return (pow(2,N-1));
}
451 views
0 replies
0 upvotes
Interview problems
C++ Solution .
int numberOfNodes(int N){
// Write your code here.
return pow(2,N-1);
}
253 views
0 replies
0 upvotes
Interview problems
Different thinking must check once
int numberOfNodes(int N){
if(N==0) {
return 0;
}
if(N==1) {
return 1;
}
if(N==2) {
return 2;
}
int ans = 0;
if(N >= 3) {
ans = pow(2, N) - pow(2,N-1);
}
return ans;
} 225 views
0 replies
0 upvotes
Interview problems
c++
one line of code int numberOfNodes(int N){
// Write your code here.
return pow(2,N)/2;
}
236 views
0 replies
1 upvote
Interview problems
easy Python code
from typing import *
def numberOfNodes(N : int) -> int:
return 2**(N-1)
if u find the code correct plz upvote..
114 views
0 replies
1 upvote
Interview problems
java one line code
int result = ((int)Math.pow(2,N))/2;
return result;
159 views
0 replies
0 upvotes
1
2
3
4
C++ (g++ 5.4)
Console