Talk:Lowest common ancestor

From Wikipedia, the free encyclopedia

@David Eppstein: the binary tree in my implemetation doesn't have to be balanced (I know that pictures suggest that), as long as nodes have proper numbering. (This isn't big problem, since the depth of BT can be remembered while building BT and BT depth can be used to for calculation of node's number). GiM 18:47, 13 June 2007 (UTC)

It does have to be balanced (by which I mean, not necessarily a complete binary tree, but having relatively small depth) because, if I understand it correctly, the numbering you use assumes that the depth of the tree is less than the number of bits per word. —David Eppstein 19:55, 13 June 2007 (UTC)

If I understand you correctly, yes. The maximum depth of BT is number_of_bits_in_word - 1 (so that would be 31, which is rather small). That is definitely limitation. Thanks for clearing this out. —GiM 10:35, 14 June 2007 (UTC)