Get the depth of a node in a Ternary Tree Using The Indexes in Array Implementation of Trees

Question

Let's assume we create a Ternary tree using an array implementation. The root is stored in the index 1, the left child is stored in index = 3(index)-1, middle child is stored in 3(index), and right child is stored in 3(index)+1. So for example. Assume the following Ternary Tree.

                                    A
                    B               C             D
                 E  F  G         H  I  J       K  L  M

The array implementation would be [None, A, B, C, D, E, F, G, H, I, J, K, L, M]

If we take F for random, F is the middle child go B, and B is the left child of A. A has an index of 1, so B has an index of 2, so F has an index of 6.

My question is, how can I get the depth from the indexes. F has an index of 6 and a depth of 2. If this was a binary tree, the depth would simply be equal to int(math.log(index, 2)). What is the equation for the depth for a ternary tree, I can't think of any.

Answer 1

The formula is int(math.log(2*index - 1, 3))

You can derive it as follows:

Each level has a number of nodes that is a power of 3. So the position of the last node in a level is a sum of such powers, which forms a geometric series. This means the index of the last node on level 𝑛 (zero based) is (3^𝑛─1)/2. Solving this to 𝑛, and taking into account the dummy entry in the array, this gives the final solution at the top.

Answer 2

The number of nodes in level k is 3**k, for level 0 it's 1, for level 1 it's 3, for level 2 it's 9, and so on. The total number of nodes in k levels is the sum of arithmetic progression:

sum(i in [0;k], 3**i) = (1 + 3**k)*(k+1) / 2

For a node index N you need to find such k that:

(1 + 3**k)*(k+1)/2 <= N < (1 + 3**(k+1))*(k+2) / 2

I would suggest binary search to find k given N, as it's a programming problem, not mathematical.

But you can also try to solve the equation by taking the natural logarithm of its parts, for N>1 it should keep the inequality sign. I'll leave this to you as an excersize, otherwise you can ask in the Mathematics stack exchange.