Using Leaf Count to Find Total Number of Nodes in a Full K-Ary Tree

1. Introduction

In this tutorial, we’ll discuss the problem of calculating the total number of nodes in a full $\textbf{k}$ -Ary tree. For that, we’ll first explore the iterative and recursive approaches, followed by a purely mathematical approach.

2. Full $\huge\textbf{k}$ -Ary Tree

Let’s start by familiarizing ourselves with a full $k$ -ary tree:

We can see here that all nodes except the leaf nodes have $\textbf{k}$ children (in this case, $k=3$ ).

Further, the problem asks us to calculate the total number of nodes in the tree when we know the total number of leaves ( $L$ ). For this case, we can count and tell that the total number of leaves is $27$ , while the total number of nodes is $40$ .

For all positive integers, $\textbf{k}\bm\geq\textbf{2}$ , we can find the total number of nodes, just by knowing the total number of leaves.

3. Iterative Solution

The total number of nodes is essentially the summation of the count of nodes at each level of the tree. Let’s see how we can do this iteratively.

3.1. Algorithm Flow

In the iterative approach, we start from the leaf nodes and walk our way upwards towards the root of the tree. As each node in a full $k$ -ary tree has $k$ children, the total number of nodes at a level is $\textbf{k}$ times that of the level above it.

So, in each iteration, we go one level up and increment the total number of nodes so far by the number of nodes present in the current level:

To safeguard from erroneous input values, we can include validation checks and exit with error in case of invalid input.

3.2. Pseudocode

Let’s look at the pseudocode implementation of the iterative approach:

function ComputeTotalNodes(leaves, k):
    // INPUT
    //   leaves = Total number of leaves
    //   k = Order of a full k-ary tree
    // OUTPUT
    //   Returns the total number of nodes in the tree

    if k < 2 or leaves < 0:
        return error "Invalid Input"

    total <- leaves
    count <- leaves
    finished <- false
    while count > 0 and count mod k = 0:
        count <- count / k
        total <- total + count

        if count = 1:
            finished <- true
            break

    if not finished:
        return error "Invalid Input"

    return total

We start by initializing the total number of nodes ( $total$ ) and count of nodes at the current level ( $count$ ) as the number of leaves. In each iteration, $count$ is reduced by a factor of $k$ , while $total$ is incremented by the count of nodes at the current level.

Finally, we stop when the count of nodes at the current level reaches a value of $1$ , implying that we have reached the root of the tree.

4. Recursive Solution

The same algorithm idea can be implemented using a recursive approach. Let’s see how we can replace the loop with a recursion.

4.1. Pseudocode

The process of counting the total number of nodes up to a certain level is essentially the same as adding the nodes of that level to the total number of nodes up to the level above it:

$\begin{equation*} \begin{alignat*}{0} T_i &= N_i + T_{i-1} & {;i \geq 1}\\ T_0 &= 1 & \end{alignat*} \end{equation*}$

$\begin{equation*} \begin{alignat*}{0} \text{Where,}&\\ T_i &: \text{Total nodes up to i\textsuperscript{th} level}\\ N_i &: \text {Total nodes at i\textsuperscript{th} level} \end{alignat*} \end{equation*}$

So, keeping this recursive formula in mind, let’s look at the pseudocode for the recursive-style implementation:

function ComputeTotalNodes(leaves, k):
    // INPUT
    //   leaves = Total number of leaves
    //   k = Order of a full k-ary tree
    // OUTPUT
    //   Total number of nodes

    if k < 2 or leaves < 0:
        error "Invalid Input"
    
    return ComputeTotalNodesRecursive(leaves, k, leaves)

function ComputeTotalNodesRecursive(count, k, total):
    // INPUT
    //   count = Number of nodes at current level
    //   k = Order of a full k-ary tree
    //   total = Total number of nodes so far
    // OUTPUT
    //   Total number of nodes

    if count mod k != 0:
        return error "Invalid Input"
    
    count <- count / k
    total <- count + total

    if count <= 1:
        return total
    else:
        return ComputeTotalNodesRecursive(count, k, total)

We can see that the function $ComputeTotalNodesRecursive$ is the core recursive part that is wrapped by the $ComputeTotalNodes$ function. There are two benefits of this abstraction:

Any pre-validations can be executed once inside the wrapper function
The client gets the same interface without any leaks of internal implementation details

5. Direct Formula Approach

Now that we understand the iterative and recursive approaches, let’s learn one more approach where we’ll delegate the core functionality to readily available mathematical functions.

5.1. Height Precomputation

Starting from the top of the tree, if we write down the total number of nodes at each level, then we’ll get the geometric progression series:

$1, k, k^2, k^3, ..., leaves$

The solution boils down to the summation of a geometric series.

So, we can make use of logarithmic and exponential functions as helper functions:

function ComputeTotalNodes(leaves, k):
    // INPUT
    //   leaves = Number of leaves
    //   k = Order of a full k-ary tree
    // OUTPUT
    //   Total number of nodes

    height <- Height(leaves, k)
    total <- (k^height - 1) / (k - 1)
    return total

function Height(leaves, k):
    // INPUT
    //   leaves = Total number of leaves
    //   k = Order of a full k-ary tree
    // OUTPUT
    //   Height of the tree

    height <- 1 + log_k(leaves)
    if height mod 1 != 0:
        error "Invalid Input"
    
    return height

By delegating the core functionality to mathematical functions, this approach looks more readable and simple.

5.2. Direct Computation

We can further simplify the formula of computing the total number of nodes by removing the intermediate step of height calculation. Let’s see it mathematically:

$\begin{equation*} \begin{align*} Height & = 1+\log_k Leaves & \\ Total & = \frac{k^{Height} - 1}{k - 1} & \\ \end{align*} \end{equation*}$

$\text{Using these equations:}$

$\begin{equation*} \begin{split} {Total} & = \frac{k^{Height} - 1}{k - 1} \\ & = \frac{k^{1 + \log_k Leaves} - 1}{k - 1} \\ & = \frac{k \times k^{\log_k Leaves} - 1}{k - 1} \\ & = \frac{{k \times Leaves} - 1}{k - 1} \\ & = Leaves + \frac{Leaves - 1}{k - 1} \end{split} \end{equation*}$

Finally, let’s arrive at a simplified version of our algorithm that uses this formula:

function ComputeTotalNodes(leaves, k):
    // INPUT
    //   leaves = Total number of leaves
    //   k = Order of a full k-ary tree
    // OUTPUT
    //   Total number of nodes

    total <- leaves + (leaves - 1) / (k - 1)

    if total mod 1 != 0:
        error "Invalid Input"

    return total

6. Complexity Analysis

All the approaches that make direct or indirect use of the height of the tree have a time complexity of $\mathbf{O(\log{}leaves)}$ . That’s because the height of the full $k$ -ary tree scales logarithmically with the order of the tree.

However, our last approach depends doesn’t require us to do any intermediate calculations. If we assume that the Arithmetic Logic Unit (ALU) supports division at the hardware level, then the time complexity of our algorithm would be $\mathbf{O(1)}$ . Otherwise, even the last algorithm will have a time complexity of $\mathbf{O(\log{}leaves)}$ .

7. Conclusion

In this tutorial, we covered different approaches to calculate the total number of nodes of a full $k$ -ary tree. We started from scratch using the iterative and recursive approaches and concluded with a direct mathematical formula based approach.

Core Concepts

Operating Systems

Artificial Intelligence

Graph Theory

Latex

Full Archive

About Baeldung