2.1) Size of Binary Tree

Size of Binary Tree:

The size of a Binary Tree is the total number of nodes present in the tree.

It represents the count of nodes, which includes both internal nodes (with children) and leaf nodes (without children).

Calculating the size of a Binary Tree involves traversing the tree and counting the nodes.

Consider the following Binary Tree:

        5
      /   \
     3     8
    / \   / \
   2   4 6   10

The size of this Binary Tree is 7 because it contains 7 nodes: {2, 3, 4, 5, 6, 8, 10}.

How to Calculate Size of Binary Tree:

To calculate the size of a Binary Tree, you can use a recursive approach. The idea is to traverse the tree and at each node, calculate the size of its left and right subtrees. The size of the current node’s subtree is the sum of sizes of its left and right subtrees, plus 1 (for the current node itself).

Here’s how the algorithm works:

1. If the tree is empty (root is nullptr), the size is 0.
2. If the tree is not empty:
   a. Recursively calculate the size of the left subtree.
   b. Recursively calculate the size of the right subtree.
   c. The size of the current node’s subtree is the sum of sizes of the left and right subtrees, plus 1.

This algorithm efficiently counts all the nodes in the tree and gives you the size of the Binary Tree.

Time and Space Complexity:

The time complexity of finding the size of a Binary Tree is O(n), where n is the number of nodes in the tree. This is because you need to visit every node once.

The space complexity is O(h), where h is the height of the tree, due to the space used by the recursive function call stack.

Use Cases:

Knowing the size of a Binary Tree can be helpful in various scenarios, such as:

1. Memory Management: When allocating memory dynamically for a Binary Tree, knowing its size helps in proper memory management and allocation.
2. Performance Analysis: Understanding the size of a Binary Tree is important for analyzing the performance of algorithms that operate on trees, such as searching, insertion, and deletion.
3. Resource Allocation: In some cases, you might need to allocate resources based on the size of the Binary Tree, such as allocating an array to store values from the tree.
4. Problem Solving: Many coding problems involving Binary Trees require knowledge of the tree’s size as a part of the solution.

C++ Code to find Size of Binary Tree:

#include <iostream>

// Define a node structure for the Binary Tree
struct Node {
    int data;
    Node* left;
    Node* right;

    Node(int value) {
        data = value;
        left = nullptr;
        right = nullptr;
    }
};

// Function to find the size of Binary Tree
int treeSize(Node* root) {
    if (root == nullptr)
        return 0;

    // Recursively calculate the size of left and right subtrees
    int leftSize = treeSize(root->left);
    int rightSize = treeSize(root->right);

    // Return the size of the current node's subtree
    return leftSize + rightSize + 1;
}

int main() {
    // Creating the Binary Tree
    Node* root = new Node(5);
    root->left = new Node(3);
    root->right = new Node(8);
    root->left->left = new Node(2);
    root->left->right = new Node(4);
    root->right->left = new Node(6);
    root->right->right = new Node(10);

    // Calculate and print the size of the Binary Tree
    int size = treeSize(root);
    std::cout << "Size of Binary Tree: " << size << std::endl;

    return 0;
}

Code Explanation:

• We define a Node structure for the Binary Tree, holding data, a left child, and a right child.
• The treeSize function recursively calculates the size of the Binary Tree. For each node, it adds the sizes of its left and right subtrees, plus 1 for the current node.
• In the main function, we create the Binary Tree and call treeSize to calculate and print the size of the tree.

When you run the code, it calculates and prints the size of the given Binary Tree, which is 7 in this case.

Output:

Size of Binary Tree: 7