Solution Review: Calculating the Size of a Tree

In this lesson, we will review a solution to the problem of determining the size of a binary tree.

The “size” of a binary tree is the total number of nodes present in the binary tree. We will explicitly define this quantity in greater detail and cover a strategy for how one may calculate this quantity in the binary tree data structure we have been building in this chapter.

We will discuss an iterative and a recursive approach for solving this challenge.

Iterative Approach

In the iterative solution, we’ll make use of a stack on which we can push the starting node and increment size by 1. Next, we’ll pop elements and push their children on to the stack if they have any. For every push, we’ll increment size by 1. When the stack becomes empty, the count for the size will also be final. Have a look at the slides below to check out the algorithm: