Defining the youngest child node (the child with the highest index) in an array-based binary tree in O (1)?

Question

Some binary tree structures (such as heaps) can be implemented using an array by setting indices from left to right, from top to bottom

  0
       / \
      12
    / \ / \
   3 4 5 6
  / \ / \ / \ / \
 7 8 9 10 11 12 13 14
        ... etc.

Children and the parent element of node at index x can easily be found in O (1):

  child-left (x) = 2x + 1
 child-right (x) = 2x + 2
 parent (x) = (x-1) / 2

But is there a way to find the smallest descendant of x in O (1) (i.e. the descendant with the highest index)? For example, in the above tree, the smallest child x=0 will be 14, and for x=1 - 10 . Note that for x=1 , if there were only 10 elements in the tree, it should return 9 .

I can assume that in my array there will be no more than 2 ³² elements, therefore in O (1) it is possible to implement 2 ⁿ using bit shifts. Maybe log_2 (???)

Answer 1

Well, I figured it out. The depth of node x is

  depth (x) = log2 (x + 1)

Similarly, you can easily find the ith left and ith right numbers from node x :

  ithLeftChild (x, i) = 2 i (x + 1) - 1
 ithRightChild (x, i) = 2 i (x + 2) - 2

The index of the leftmost child at depth d is ithLeftChild(x, d - depth(x)) and similarly for the right child.

Call the index of the last element n . So, now we can find the depth n , and we can also find the signs leftmostChild and rightmostChild at that depth (which may be larger than the last element, which means that they actually do not exist).

Now we have only three cases:

• n < leftmostChild . Then our subtree has no elements at this depth, so the highest index should be parent(rightmostChild) .
• leftmostChild <= n <= rightmostChild . Then the highest index is necessarily n .
• rightmostChild < n . Then rightmostChild should be our highest index.

---

2 ⁱ can be implemented in O (1) for reasonable i using bit shifts; log2(x) can be implemented in O (1) using a 256-byte lookup table . Thus, the general algorithm is O (1) .