GATE 1990
February 13, 2024Question 4365 – 2009 June UGC NET Paper 1
February 13, 2024GATE 1990
|
Question 12
|
Choose the correct alternatives (More than one may be correct).
The total external path length, EPL, of a binary tree with n external nodes is, EPL = ∑wIw, where Iw is the path length of external node w),
|
≤ n2 always.
|
|
|
≥ n log2 n always.
|
|
|
Equal to n2 always.
|
|
|
O(n) for some special trees.
|
Question 12 Explanation:
Here the question asked for binary tree.
It can be of 2 types:
1) Skewed tree.
2) Balanced binary tree or AVL tree.
We have to find external path length, i.e., leaf node.
We also know cost of external path = leaf node value + length of path
Now for balanced tree external path length = n × log n
But for skewed tree it will be O(n) only.
So, answer will be (D).
It can be of 2 types:
1) Skewed tree.
2) Balanced binary tree or AVL tree.
We have to find external path length, i.e., leaf node.
We also know cost of external path = leaf node value + length of path
Now for balanced tree external path length = n × log n
But for skewed tree it will be O(n) only.
So, answer will be (D).
Correct Answer: D
Question 12 Explanation:
Here the question asked for binary tree.
It can be of 2 types:
1) Skewed tree.
2) Balanced binary tree or AVL tree.
We have to find external path length, i.e., leaf node.
We also know cost of external path = leaf node value + length of path
Now for balanced tree external path length = n × log n
But for skewed tree it will be O(n) only.
So, answer will be (D).
It can be of 2 types:
1) Skewed tree.
2) Balanced binary tree or AVL tree.
We have to find external path length, i.e., leaf node.
We also know cost of external path = leaf node value + length of path
Now for balanced tree external path length = n × log n
But for skewed tree it will be O(n) only.
So, answer will be (D).