retagged by
411 views

2 Answers

Best answer
2 votes
2 votes

We can understand it intuitively in this way - Traverse the entire tree using any Tree Traversal Algorithm of your choice and keep track of nodes that have no descendants (leaf nodes). A tree traversal algorithm won't take more than $O(n)$ in the worst case, where $n$ is the number of nodes in a tree.

Here is a recursive algorithm for better understanding -

int countLeaves(Node node){
  if( node == null )
    return 0;
  if( node.left == null && node.right == null ) 
    return 1;
  else 
    return countLeaves(node.left) + countLeaves(node.right);
}
selected by

Related questions

2 votes
2 votes
1 answer
1
5 votes
5 votes
2 answers
2
Aboveallplayer asked Jan 15, 2017
1,484 views
int x=0;int A(n){ statement //takes O(1) time if(n==1) return 1; else { $X+=8.A\left ( \frac{n}{2}\right )+n^3$; } return X;}What is the time com...
0 votes
0 votes
1 answer
3
rajan asked Dec 9, 2016
352 views
how to solve these two using matser thorem.1. t(n)=2t(√n)+n2. t(n)=4t(√n)+(logn)^2
1 votes
1 votes
2 answers
4
vijaycs asked Jul 11, 2016
1,842 views
On which of the following recurrence relation Masters theorem can not be applied ?A. T(n)= 2T(n/2) + n (log n).B. T(n) = T(n/2) + 1.C. T(n) = 8T(n/2) + (log n).D. T(n) = ...