Question

A $\mathbf{d}$-ary tree is a rooted tree in which each node has at most $\mathbf{d}$children. Show that any $\mathbf{d}$-ary tree with $\mathbf{n}$ nodes must have a depth of$\mathbf{\Omega }\left(\frac{\mathrm{logn}}{\mathrm{logd}}\right)$ .Can you give a precise formula for the minimum depth it could possibly have?

Short answer

The depth of $\mathrm{n}$ node is equal to $\mathrm{\Omega }\left(\frac{\log \mathrm{n}}{\log \mathrm{d}}\right)$. Minimum depth of $d$-ary tree with $n$ nodes is $\Omega \left(\frac{\log \mathrm{n}}{\log \mathrm{d}}\right)$.

Step-by-step solution

Find the number of vertices and nodes

A $d$-ary tree is defined as a $d$-heap which is a priority queue data structure that contains $d$number of nodes in place of two nodes.

Assume that the difference between left and right subtree is not greater than $1$ by height and every node is having $d$ times more node than upper level.

So, number of vertices at level $\mathrm{n}$ is

$\mathbf{V}\mathbf{=}{\mathbf{d}}^{\mathbf{n}}$

And number of nodes at depth is

$\mathbf{H}\mathbf{=}{\mathbf{d}}^{\mathbf{n}}$

Calculate total number of nodes of the tree

Number of nodes at each level are:

$\begin{array}{c}\mathrm{Level}1=1\\ \mathrm{Level}2=\mathrm{d}\\ \mathrm{Level}3={\mathrm{d}}^2\\ \mathrm{Level}4={\mathrm{d}}^3\end{array}$

Number of nodes at level $h+1$ is ${\mathrm{d}}^{\mathrm{h}}$.

So, it forms a geometric series $1+\mathrm{d}+{\mathrm{d}}^2+{\mathrm{d}}^3+\mathrm{...}+{\mathrm{d}}^{\mathrm{h}}$

First element $a$ by removing $1$ from series is $d$.

Common ratio $=d$

Sum of the total nodes of the tree$\frac{{\mathrm{d}}^{\mathrm{h}+1}-1}{\mathrm{d}-1}$.

Let number of nodes in a tree is $n$.

Then,

$\begin{array}{c}{\mathrm{d}}^{\mathrm{h}+1}=\mathrm{n}\times (\mathrm{d}-1)+1\\ {\mathrm{d}}^{{(\mathrm{h}+1)}^3}=\mathrm{n}+1\\ \end{array}$

Taking log on both sides: $\log \left({\mathrm{d}}^{{(\mathrm{h}+1)}^3}\right)=\log (\mathrm{n}+1)$

So, ${\mathrm{h}}^3\frac{\mathrm{logn}}{\mathrm{logd}}$ . It is defined as ${\mathrm{h}}^3\mathrm{\Omega }\left(\frac{\log \mathrm{n}}{\log \mathrm{d}}\right)$

So, the depth of $n$ node is equal to $\Omega \left(\frac{\log n}{\log d}\right)$. Minimum depth of $d$-ary tree with $n$ nodes is$\Omega \left(\frac{\log n}{\log d}\right)$ .