Talk:Lowest common ancestor

From Wikipedia, the free encyclopedia
Jump to: navigation, search
WikiProject Computer science (Rated Start-class)
WikiProject icon This article is within the scope of WikiProject Computer science, a collaborative effort to improve the coverage of Computer science related articles on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.
Start-Class article Start  This article has been rated as Start-Class on the project's quality scale.
 ???  This article has not yet received a rating on the project's importance scale.
 
WikiProject Mathematics (Rated Start-class, Mid-importance)
WikiProject Mathematics
This article is within the scope of WikiProject Mathematics, a collaborative effort to improve the coverage of Mathematics on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.
Mathematics rating:
Start Class
Mid Importance
 Field:  Discrete mathematics

[untitled][edit]

@David Eppstein: the binary tree in my implementation 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)