Question

What is the condition for a tree to be weight balanced. where a is factor and n is a node?

(a) weight[n.left] >= a*weight[n] and weight[n.right] >= a*weight[n].

(b) weight[n.left] >= a*weight[n.right] and weight[n.right] >= a*weight[n].

(c) weight[n.left] >= a*weight[n.left] and weight[n.right] >= a*weight[n].

(d) weight[n] is a non zero

My question is taken from Weight Balanced Tree topic in section Binary Trees of Data Structures & Algorithms I

This question was addressed to me during an interview.

Answer 1

Right option is (a) weight[n.left] >= a*weight[n] and weight[n.right] >= a*weight[n].

For explanation: The tree is said to be a-balanced if the condition is satisfied. and ‘a’ value will be determined during tree formation. large value of ‘a’ is more effective.