1

I have a control which may contain child controls of the same type. These controls have been linked together such that they form a tree structure.

Now, given a list of X controls present in this tree, I would like to find the closest common parent control of all controls in my list. I do not know the location of my child controls in the tree.

More than willing to do some thinking on this issue, but I can only assume that it has already been solved optimally. Does anyone know where I can find this algorithm? If not, suggested approach or reading?

enter image description here

LarsTech
  • 80,625
  • 14
  • 153
  • 225
Sean Anderson
  • 27,963
  • 30
  • 126
  • 237
  • It sounds like a panel inside a panel inside a panel, and then a listbox next to it show the name of every panel. Something like that? – LarsTech Jul 13 '11 at 20:14
  • Yeah, pretty much. :) I've uploaded an IMG to the initial post visualizing my problem. – Sean Anderson Jul 13 '11 at 20:19
  • Wish I could +10. This is a great little puzzler. Seems it's been asked before :) http://stackoverflow.com/questions/1484473/how-can-i-find-the-common-ancestor-of-two-nodes-in-a-binary-tree – Martin Jul 13 '11 at 20:31
  • Hey, thanks! I didn't see it had been posted. Should I mark this as duplicate – Sean Anderson Jul 13 '11 at 20:36

2 Answers2

1

Wikipedia has a few articles on the issue:

General Theory: Lowest common ancestor

Some implementations: Tarjan's off-line least common ancestors algorithm

Martin
  • 39,569
  • 20
  • 99
  • 130
1

As Tarjan's off-line least common ancestors is offline, you may wish to approach the problem by another route. Using a bredth-first or depth-first search, find the path's of each item in your search list. Then, you can use these paths to determine the lowest common ancestor.

The psuedo-code would be something like:

  1. iterate over all nodes in tree
  2. if node is in search list, record path (from node ids)
  3. after all nodes have been searched, start at the first path id of each search list node
  4. if first id is identical for all nodes move to next id
  5. repeat step 4 until at least one id is different. The previous id is the least common ancestor.

For example, with your search list example of , you would build the following path index

H -> ABDH I -> ABEI J -> ABEJ E -> ABE

Now, you can see all nodes have a A at position 1. As well as a B at position 2. However, at position 3, H has a D which doesn't match the other nodes. Thus node B is the least common ancestor.

Obviously there are corner cases. If the search list has only one item, it is the least common ancestor. Likewise, if you are comparing the paths and you reach the node itself, it is the common ancestor.

Mark Schadler
  • 126
  • 4