Bloomberg LP Interview Question
Financial Software DevelopersBy balanced it is meant that the tree does not degenerate into a link list with each node just having either left or right children. For it to be balanced the height of the tree should be O(n) which only happens when children are equally divided between left and right subtrees.
Well, if there is no constraint of balance, this may be a case of simple insertions in a binary search tree with complexity of 0(logn). If balance is a constraint, then probably a red-black tree may be a way to go, with the same complexity of O(logn).Comments are welcome
- amit October 10, 2009