luvtheedragon
BAN USERhere is how I would do it:
1. if it is a BST, the find operation can be altered such that it does a search for not just 1 element but 2 elements, and when the decision is coincidental, go ahead in that direction. whenever the first contradiction occurs, return a pointer to the current node.
2. if it is not a BST, you can use the property that the node asked for is the only node for which the 2 nodes lie in different subtrees. for all nodes above it, they lie in the same subtree. for all nodes below it, one of the node doesn't exist.
I dont think that you can get around the requirement of interating thru both the lists, and comparing each element, for the simple reason that not only do you have to ensure that the element exists in both the lists, but also at the same position.
- luvtheedragon February 17, 2010if height is a parameter of the node, then a O(height) = O(logN) can be achieved. here is the algorithm:
1. find the diameter at the node, as the sum of left->height + right->height + 1
2. follow the path from node to the node at max depth node.
mathematically, it can be argued that the max depth node at the root of the tree will remain the max node for every subtree, and thus will be a part of the diameter of the tree, whether or not the current node lies on the diameter.
gr8!
- luvtheedragon February 16, 2010order statistics
- luvtheedragon February 16, 2010en.wikipedia.org/wiki/Threaded_binary_tree
- luvtheedragon February 15, 2010
RepHuge collection of cheap ammo for Rifle, Handgun, Shotgun & Rimfire from top brands you are looking for.
@ryan ...
- luvtheedragon February 20, 2010for a non BST ( m-tree ) here is how you can do it ....
if you do a find operations, and find a direct path from the root to each of the nodes, storing the return path from the each of node to root. store the intermediate root pointers in a list. compare the lists in the reverse order, and you have the deepest common ancestor.