1. Introduction
In this tutorial, we’ll discuss the problem of calculating the total number of nodes in a full -Ary tree. For that, we’ll first explore the iterative and recursive approaches, followed by a purely mathematical approach.
2. Full -Ary Tree
Let’s start by familiarizing ourselves with a full -ary tree:
We can see here that all nodes except the leaf nodes have children (in this case, ).
Further, the problem asks us to calculate the total number of nodes in the tree when we know the total number of leaves (). For this case, we can count and tell that the total number of leaves is , while the total number of nodes is .
For all positive integers, , 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 -ary tree has children, the total number of nodes at a level is 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 () and count of nodes at the current level () as the number of leaves. In each iteration, is reduced by a factor of , while 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 , 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:
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 is the core recursive part that is wrapped by the 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:
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:
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 . That’s because the height of the full -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 . Otherwise, even the last algorithm will have a time complexity of .
7. Conclusion
In this tutorial, we covered different approaches to calculate the total number of nodes of a full -ary tree. We started from scratch using the iterative and recursive approaches and concluded with a direct mathematical formula based approach.