Register

GATE Overflow | Data Structures | Test 1 | Question: 16

1,158 views
6 votes
6 votes

A program takes as input a binary tree (not necessarily balanced) with $n$ nodes and computes for each node, the no. of leaf nodes in the sub-tree rooted at that node. The worst case time complexity of the program is

  1. $\Theta(n)$
  2. $\Theta(n \log n)$
  3. $\Theta\left(n^2 \right)$
  4. $\Theta\left(n^2 \log n \right)$
User Avatar

5 Answers

0 votes
0 votes
What would be the answer if, we are asked to compute number of nodes in the subtree rooted at each node of the binary tree?
User Avatar
Page:
Voting & Accepting an answer helps improve the community
Answer:
← PreviousNext →
← Previous in categoryNext in category →

Related questions

0 votes
0 votes
1 answer
6
Arjun asked Oct 10, 2016
309 views
GATE Overflow | Data Structures | Test 1 | Question: 14
Consider the array given below: 20 10 9 8 7 6 5 It is a full binary tree in array representation a complete binary tree in array representation a max-heap in array representation all of the above
Consider the array given below:20 10 9 8 7 6 5It isa full binary tree in array representationa complete binary tree in array representationa max-heap in array representat...
User Avatar
1 votes
1 votes
2 answers
7
Arjun asked Oct 10, 2016
829 views
GATE Overflow | Data Structures | Test 1 | Question: 10
With 5 distinct nodes, the maximum no. of binary trees that can be formed is _____
With 5 distinct nodes, the maximum no. of binary trees that can be formed is _____
User Avatar
Link Copied!