Finding the Size of a Tree
Introduction
A common operation when working with trees is finding the size of a tree, which refers to counting the total number of nodes in the tree. One of the most common and intuitive ways to find the size of a tree is through a recursive approach. This method involves traversing the tree and counting the nodes using a recursive function.
In this guide, we will explore methods to determine the size of a binary tree.
What is the Size of a Tree?
The size of a tree is a straightforward concept—it represents the number of nodes in the tree. In a binary tree, it’s the total count of nodes, including both internal nodes (those with child nodes) and leaf nodes (those without children).
Finding the Size of a Tree Example
Consider a Binary Tree : Let us take an example.
The tree depicted above has a size of 7.
- To determine the tree’s size, we calculate it by adding the sizes of its left and right subtrees and then incrementing the result by 1.
- This process involves invoking a recursive function for both the left and right subtrees of the tree. If a subtree is absent, the function returns 0.
Above Example Analysis 📊
The above example for finding the size of a tree is depicted as below :
- Size of node 13 = Size(11) + Size(15) + 1
- Size of node 13 = (Size(9) + Size(12) + 1) + (Size(14) + Size(17) + 1) + 1
- Size of node 13 = (Size(9) + Size(12) + 1) + (Size(14) + Size(17) + 1) + 1
- Size of node 13 = (1 + 1 + 1) + (1 + 1 + 1) + 1
- Size of node 13 = 7
How to Calculate the Size of a Tree in Data Structure
A straightforward approach:
- Begin at the root.
- The size is determined by adding 1 (for the root) to the sizes of the left sub-tree and the right sub-tree.
- Resolve the sizes of the left and right sub-trees through recursive calculations.
Prime Course Trailer
Related Banners
Get PrepInsta Prime & get Access to all 200+ courses offered by PrepInsta in One Subscription
Methods for Finding the Size of a Tree
There are mainly two approaches for finding the size of a tree :
Recursive Method
Iterative Method
Recursive Approach
One of the most common and intuitive ways to find the size of a tree is through a recursive approach. This method involves traversing the tree and counting the nodes using a recursive function. Here’s a simple example in Python:
Code :
class Node:
def __init__(self, data):
self.data = data
self.left = None
self.right = None
def treeSize(root):
if root is None:
return 0
else:
return 1 + treeSize(root.left) + treeSize(root.right)
Iterative Approach
Another way to find the size of a tree is through an iterative approach, often utilizing a level order traversal (Breadth-First Search or BFS). The idea here is to start at the root node and traverse the tree while keeping track of the count. Below is an example of an iterative implementation in Python:
Code :
def treeSizeIterative(root):
if root is None:
return 0
size = 0
queue = []
queue.append(root)
while queue:
node = queue.pop(0)
size += 1
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
return size
Implementation of Finding the Size of a Tree
Code :
class Node:
def __init__(self, data):
self.data = data
self.left = None
self.right = None
# Recursive approach to find the size of a tree
def treeSizeRecursive(root):
if root is None:
return 0
else:
size = 1 + treeSizeRecursive(root.left) + treeSizeRecursive(root.right)
return "Size of the tree (recursive): " + str(size)
# Iterative approach to find the size of a tree
def treeSizeIterative(root):
if root is None:
return 0
size = 0
queue = []
queue.append(root)
while queue:
node = queue.pop(0)
size += 1
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
return "Size of the tree (iterative): " + str(size)
# Example usage (creating a binary tree)
root = Node(1)
root.left = Node(2)
root.right = Node(3)
root.left.left = Node(4)
root.left.right = Node(5)
root.right.left = Node(6)
root.right.right = Node(7)
# Using the recursive approach to find the size of the tree
tree_size_recursive = treeSizeRecursive(root)
print(tree_size_recursive)
# Using the iterative approach to find the size of the tree
tree_size_iterative = treeSizeIterative(root)
print(tree_size_iterative)
Output :
Size of the tree (recursive): 7 Size of the tree (iterative): 7
Explanation :
The code computes the size of a binary tree using both recursive and iterative methods. It finds the total number of nodes in the tree. The recursive approach uses a function that counts nodes by recursively traversing the tree. The iterative approach employs a queue for a level-order traversal to count the nodes iteratively. Both methods yield the same result of 7 for the given example tree.
Applications
Following are the applications of finding the size of a tree :
To Wrap it up:
In conclusion, Calculating the size of a tree is a fundamental operation when working with trees. Depending on your preferences and specific use cases, you can choose between a recursive or an iterative approach to find the size of a tree. Both methods are effective, and you can select the one that best fits your requirements.
Question 1.
What does “size of a tree” mean?
The size of a tree refers to the total number of nodes in the tree, including both internal (with children) and leaf nodes (without children).
Question 2.
Can I use the size of a tree to determine its height?
Yes, you can calculate the height of a tree using the size. The height is the longest path from the root to a leaf node, which can be found by finding the log base 2 of the size (in the case of a balanced binary tree).
Question 3.
How do I adapt the size-finding methods to n-ary trees or other tree structures?
The basic principles for finding the size of a binary tree can be adapted to n-ary trees by modifying the traversal and counting logic.
Get over 200+ course One Subscription
Courses like AI/ML, Cloud Computing, Ethical Hacking, C, C++, Java, Python, DSA (All Languages), Competitive Coding (All Languages), TCS, Infosys, Wipro, Amazon, DBMS, SQL and others
Login/Signup to comment