CODEWITHSUNDEEP
algorithmbinary-tree
Tryer
Tryer

Reputation: 4080

Finding common parent in perfect binary tree

This question:

Are there any efficient ways to populate a balanced tree structure

provides an analytical way of labelling a perfect binary tree of any depth.

In such a tree, is there any way of efficiently figuring out the first common parent of an arbitrary subset of leaf nodes?

For instance, given the following binary tree:

enter image description here

I am looking for a way where if:

Input is: 3,5 Output is: 0

Input is: 3,5,6 Output is: 0

Input is: 3,4 Output is: 1

The only way I can think of is to traverse up to the root (0) from each of the given leaf nodes, and then picking the first common one.

Is there any closed-form analytical way in which the first common parent can be found?

Upvotes: 0

Views: 296

Answers (1)

ardenit
ardenit

Reputation: 3890

Let H be height of your tree, and let k be the count of numbers in your input.

If you start numeration of nodes from 1 and write nodes' binary numbers, it will become clear that number of every node is prefix of numbers of all its children. So, to find the lowest common ancestor, you should find the greatest common prefix (GCP) of binary numbers.

image

Let min and max be minimal and maximal numbers in your subset. If numbers in your input are already sorted, your can find min and max in O(1). If they are not sorted, you can find min and max in O(k * H).

The GCP of all binary numbers is the GCP of min and max - you can find it trivially in O(H).

This algorithm works in O(H) if numbers are sorted and in O(k * H) otherwise (although your algorithm works in O(k * H) too if you implement it right).

Upvotes: 4

Related Questions