Using Breadth First Search Algorithm to Count the Number of Leaves and Internal Nodes in Binary Tree

Given the root to a binary tree root, return a list of two numbers where the first number is the number of leaves in the tree and the second number is the number of internal (non-leaf) nodes.

Constraints
n ≤ 100,000 where n is the number of nodes in root
Example 1
Input

  1
 / \
5   3

Output
[2, 1]
Explanation
This tree has 2 leaves and 1 internal node.

Partition Tree using BFS Algorithm

We can perform a Breadth First Search Algorithm to traverse the binary tree and then count the number of internal nodes and leaves nodes along the way. A node is a leaf node if it doesn’t have any children.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

/**
 * class Tree {
 *     public:
 *         int val;
 *         Tree *left;
 *         Tree *right;
 * };
 */
vector<int> partitionTree(Tree* root) {
    if (!root) return {0, 0};
    queue<Tree*> Q;
    Q.push(root);
    int leaves = 0, others = 0;
    while (!Q.empty()) {
        auto p = Q.front();
        Q.pop();
        if (p->left) Q.push(p->left);
        if (p->right) Q.push(p->right);
        if (p->left || p->right) {
            others ++;
        } else {
            leaves ++;
        }
    }
    return {leaves, others};
}

/**
 * class Tree {
 *     public:
 *         int val;
 *         Tree *left;
 *         Tree *right;
 * };
 */
vector<int> partitionTree(Tree* root) {
    if (!root) return {0, 0};
    queue<Tree*> Q;
    Q.push(root);
    int leaves = 0, others = 0;
    while (!Q.empty()) {
        auto p = Q.front();
        Q.pop();
        if (p->left) Q.push(p->left);
        if (p->right) Q.push(p->right);
        if (p->left || p->right) {
            others ++;
        } else {
            leaves ++;
        }
    }
    return {leaves, others};
}

The time complexity of a usual BFS implementation is O(N) where N is the number of the nodes in the binary tree. And the space complexity is usually O(N) as we need a queue to implement a classic Breadth First Search Algorithm.

–EOF (The Ultimate Computing & Technology Blog) —