A weight-balanced tree is a binary tree in which for each node. The number of nodes in the left sub tree is at least half and at most twice the number of nodes in the right sub tree. The maximum possible height (number of nodes on the path from the root to the farthest leaf) of such a tree on n nodes is best described by which of the following?a)log2nb)c)log3nd)Correct answer is option 'D'. Can you explain this answer? - EduRev Computer Science Engineering (CSE) Question

Explore Courses UPSC Exam UPSC Test Series Free Notes EduRev Infinity

Open App

Computer Science Engineering (CSE) Exam > Computer Science Engineering (CSE) Questions > A weight-balanced tree is a binary tree in wh...

Join the Discussion on the App

A weight-balanced tree is a binary tree in which for each node. The number of nodes in the left sub tree is at least half and at most twice the number of nodes in the right sub tree. The maximum possible height (number of nodes on the path from the root to the farthest leaf) of such a tree on n nodes is best described by which of the following?

a)
log₂ n
b)
c)
log₃ n
d)

Correct answer is option 'D'. Can you explain this answer?

FREE This question is part of

Test: Trees- 1

Attempt Test

Attempt this Test

Verified Answer

A weight-balanced tree is a binary tree in which for each node. The nu...

Let the maximum possible height of a tree with n nodes is represented by H(n). The maximum possible value of H(n) can be approximately written using following recursion

H(n) = H(2n/3) + 1

The solution of above recurrence is [Tex]log_{3/2} n[/Tex]. We can simply get it by drawing a recursion tree. 4. Consider the following algorithm for searching for a given number x in an unsorted - array A[1..n] having n distinct values:

1) Choose an i uniformly at random from 1..n;
2) If A[i] = x then Stop else Goto 1;

Assuming that x is present in A, what is the expected number of comparisons made by the algorithm before it terminates? a) n b) n-l c) 2n d) n/2 Answer(a) If you remember the coin and dice questions, you can just guess the answer for the above. Below is proof for the answer. Let expected number of comparisons be E. Value of E is sum of following expression for all the possible cases.

number_of_comparisons_for_a_case * probability_for_the_case

Case 1

If A[i] is found in the first attempt
number of comparisons = 1
probability of the case = 1/n

Case 2

If A[i] is found in the second attempt
number of comparisons = 2
probability of the case = (n-1)/n*1/n

Case 3

If A[i] is found in the third attempt
number of comparisons = 2
probability of the case = (n-1)/n*(n-1)/n*1/n

There are actually infinite such cases. So, we have following infinite series for E.

E = 1/n + [(n-1)/n]*[1/n]*2 + [(n-1)/n]*[(n-1)/n]*[1/n]*3 + …. (1)

After multiplying equation (1) with (n-1)/n, we get

E (n-1)/n = [(n-1)/n]*[1/n] + [(n-1)/n]*[(n-1)/n]*[1/n]*2 + [(n-1)/n]*[(n-1)/n]*[(n-1)/n]*[1/n]*3 ……….(2)

Subtracting (2) from (1), we get

E/n = 1/n + (n-1)/n*1/n + (n-1)/n*(n-1)/n*1/n + …………

The expression on right side is a GP with infinite elements. Let us apply the sum formula (a/(1-r))

E/n = [1/n]/[1-(n-1)/n] = 1
E = n

View all questions of this test

View all answers Start learning for free

< Previous Question Next Question >

Explore Courses for Computer Science Engineering (CSE) exam

Similar Computer Science Engineering (CSE) Doubts

Following function is supposed to calculate the maximum depth or height of a Binary tree — the number of nodes along the longest path from the root node down to the farthest leaf node.

View answer

Consider a Binary Tree where the allowed height difference between left and right children of every node is at most one. What are the maximum and minimum possible heights of such a Binary Tree ?

View answer

Consider the following undirected connected graph G with weights on its edges as given in the figure below. A minimum spanning tree is a spanning tree of least weight and a maximum spanning tree is one with largest weight. A second best minimum spanning tree whose weight is the smallest among all spanning trees that are not minimum spanning trees in G.Which of the following statements is TRUE in the above graph? (Note that all the edge weights are distinct in the above graph)

View answer

Consider the expression tree shown. Each leaf represents a numerical value, which can either be 0 or 1. Over all possible choices of the values at the leaves, the maximum possible value of the expression represented by the tree is ___. Correct answer is '6'. Can you explain this answer?

View answer

Following is an incorrect pseudocode for the algorithm which is supposed to determine whether a sequence of parentheses is balanced:declare a character stackwhile ( more input is availabl e){ read a character if ( the character is a ( ) push it on the stack else if ( the character is a ) and the stack is not empty ) pop a character off the stack else print "unbalanced" and exit}print "balanced"Which of these unbalanced sequences does the above code think is balanced?

View answer

Top Courses for Computer Science Engineering (CSE)View all

GATE Computer Science Engineering(CSE) 2025 Mock Test Series

Question Bank for GATE Computer Science Engineering

General Aptitude for GATE

Computer Networks

Programming and Data Structures

Top Courses for Computer Science Engineering (CSE)

View all

Share with a Friend

Answer this doubt

Question Description
A weight-balanced tree is a binary tree in which for each node. The number of nodes in the left sub tree is at least half and at most twice the number of nodes in the right sub tree. The maximum possible height (number of nodes on the path from the root to the farthest leaf) of such a tree on n nodes is best described by which of the following?a)log2nb)c)log3nd)Correct answer is option 'D'. Can you explain this answer? for Computer Science Engineering (CSE) 2024 is part of Computer Science Engineering (CSE) preparation. The Question and answers have been prepared according to the Computer Science Engineering (CSE) exam syllabus. Information about A weight-balanced tree is a binary tree in which for each node. The number of nodes in the left sub tree is at least half and at most twice the number of nodes in the right sub tree. The maximum possible height (number of nodes on the path from the root to the farthest leaf) of such a tree on n nodes is best described by which of the following?a)log2nb)c)log3nd)Correct answer is option 'D'. Can you explain this answer? covers all topics & solutions for Computer Science Engineering (CSE) 2024 Exam. Find important definitions, questions, meanings, examples, exercises and tests below for A weight-balanced tree is a binary tree in which for each node. The number of nodes in the left sub tree is at least half and at most twice the number of nodes in the right sub tree. The maximum possible height (number of nodes on the path from the root to the farthest leaf) of such a tree on n nodes is best described by which of the following?a)log2nb)c)log3nd)Correct answer is option 'D'. Can you explain this answer?.

Solutions for A weight-balanced tree is a binary tree in which for each node. The number of nodes in the left sub tree is at least half and at most twice the number of nodes in the right sub tree. The maximum possible height (number of nodes on the path from the root to the farthest leaf) of such a tree on n nodes is best described by which of the following?a)log2nb)c)log3nd)Correct answer is option 'D'. Can you explain this answer? in English & in Hindi are available as part of our courses for Computer Science Engineering (CSE). Download more important topics, notes, lectures and mock test series for Computer Science Engineering (CSE) Exam by signing up for free.

Here you can find the meaning of A weight-balanced tree is a binary tree in which for each node. The number of nodes in the left sub tree is at least half and at most twice the number of nodes in the right sub tree. The maximum possible height (number of nodes on the path from the root to the farthest leaf) of such a tree on n nodes is best described by which of the following?a)log2nb)c)log3nd)Correct answer is option 'D'. Can you explain this answer? defined & explained in the simplest way possible. Besides giving the explanation of A weight-balanced tree is a binary tree in which for each node. The number of nodes in the left sub tree is at least half and at most twice the number of nodes in the right sub tree. The maximum possible height (number of nodes on the path from the root to the farthest leaf) of such a tree on n nodes is best described by which of the following?a)log2nb)c)log3nd)Correct answer is option 'D'. Can you explain this answer?, a detailed solution for A weight-balanced tree is a binary tree in which for each node. The number of nodes in the left sub tree is at least half and at most twice the number of nodes in the right sub tree. The maximum possible height (number of nodes on the path from the root to the farthest leaf) of such a tree on n nodes is best described by which of the following?a)log2nb)c)log3nd)Correct answer is option 'D'. Can you explain this answer? has been provided alongside types of A weight-balanced tree is a binary tree in which for each node. The number of nodes in the left sub tree is at least half and at most twice the number of nodes in the right sub tree. The maximum possible height (number of nodes on the path from the root to the farthest leaf) of such a tree on n nodes is best described by which of the following?a)log2nb)c)log3nd)Correct answer is option 'D'. Can you explain this answer? theory, EduRev gives you an ample number of questions to practice A weight-balanced tree is a binary tree in which for each node. The number of nodes in the left sub tree is at least half and at most twice the number of nodes in the right sub tree. The maximum possible height (number of nodes on the path from the root to the farthest leaf) of such a tree on n nodes is best described by which of the following?a)log2nb)c)log3nd)Correct answer is option 'D'. Can you explain this answer? tests, examples and also practice Computer Science Engineering (CSE) tests.

Explore Courses for Computer Science Engineering (CSE) exam