A weight – balanced tree is a binary tree in which for

Home » Programming & Data Structure » Programming and data structure miscellaneous » Question

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 furthest leaf) of such a tree on n nodes is best described by which of the following?

1. log₂ n
2. log_{4 / 3} n
3. log₃ n
4. log_{3 / 2}n

Correct Option: D

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 log3/2 n. We can simply get it by drawing a recursion tree.