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

Category: QuestionsWhat is the condition for a tree to be weight balanced. where a is factor and n is a node?
Editor">Editor Staff asked 1 month ago

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.

1 Answers
Editor">Editor Staff answered 1 month ago

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.