Home » Data Structure

Check if a given tree has all leaves at same level or not

In this article, we are going to check whether all leaves of the given tree is at the same level or not.
Submitted by Radib Kar, on August 07, 2020

The leave nodes are the nodes that don't have any children. Now a tree can have all leaves at the same level or not. We can check that using both recursive and iterative algorithms. Below is a detailed explanation of both the approaches & also we have added examples to understand how the algorithm is working.

Example 1:

Figure 1: Example 1 where all leaf nodes are at the same level

In the above example, all the leaf nodes are marked with a double circle and we can see those are at the same level (Level 1).

Example 2:

Figure 1: Example 1 where all leaf nodes are not at the same level

In the above example, all the leaf nodes are marked with a double circle and we can see all are not at the same level (one is at Level 1 and another is at level 2).

1) Recursive approach

In the recursive method, we can calculate the level of all leaf nodes and can store that in the hash table. Then in the second pass, we will check whether all leaf nodes have the same level or not from the hash table. So, after the first pass, we will have our hash table storing all leaf nodes along with their depth. The height() function in the below implementation is computing the levels of the leaf nodes recursively and storing them in the hashmap. Then in the second pass, we have checked whether all leaf nodes are at the same level or not. Below is the detailed implementation:

C++ Implementation

#include <bits/stdc++.h>
using namespace std;

// tree node is defined
class TreeNode {
public:
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int data)
    {
        val = data;
        left = NULL;
        right = NULL;
    }
};

void height(int level, TreeNode* root, unordered_map<TreeNode*, int>& mymap)
{
    //base case
    if (!root)
        return;

    //if current node is a leaf node
    //store it along with the current level in the hash table
    if (!root->left && !root->right) {
        mymap[root] = level;
        return;
    }

    //for the next level
    height(level + 1, root->left, mymap);
    height(level + 1, root->right, mymap);
}
bool checkAllLeavesAtSameLevel(TreeNode* root)
{
    //Your code here
    if (!root)
        return true;
    //first pass to store the leaf nodes along with their levels
    unordered_map<TreeNode*, int> mymap;
    height(0, root, mymap);

    //take height of any leaf node and make that bench mark
    int bench_mark = (mymap.begin())->second;
    //comapre other leaf node levels with the bench mark
    //if any leaf node violates, return false
    for (auto it = mymap.begin(); it != mymap.end(); it++) {
        if (it->second != bench_mark)
            return false;
    }
    //if all leaf nodes are at same level return true
    return true;
}

int main()
{
    //building the tree like example 1
    TreeNode* root1 = new TreeNode(1);
    
    root1->left = new TreeNode(2);
    root1->right = new TreeNode(3);

    if (checkAllLeavesAtSameLevel(root1))
        cout << "Tree in example1 has all leaves at same level\n";
    else
        cout << "Tree in example1 doesn't has all leaves at same level\n";

    //building the tree-like example 2
    TreeNode* root2 = new TreeNode(1);
    root2->left = new TreeNode(2);
    root2->right = new TreeNode(3);
    root2->left->left = new TreeNode(4);

    if (checkAllLeavesAtSameLevel(root2))
        cout << "Tree in example2 has all leaves at same level\n";
    else
        cout << "Tree in example2 doesn't has all leaves at same level\n";
    
    return 0;
}

Output:

Tree in example1 has all leaves at same level
Tree in example2 doesn't has all leaves at same level

The time complexity of the above is O(n) and storage complexity is O(L) where L is the number of leaf nodes.

If we dry run, we will see that for the first example, after the first pass, we will have our hash table like below:

Key	                    Value
Tree Node with value 2	    1
Tree Node with value 3	    1

So all keys have the same value and hence the tree has all its leaves at the same level.

For the second example, after the first pass, we will have our hash table like below:

Key	                    Value
Tree Node with value 3	    1
Tree Node with value 4	    2

So we found that all keys don’t have the same value which means that all leaves are not at the same level.

2) Iterative approach(Using level order traversal)

We can also use iterative algorithms using level order traversal to solve this problem. The idea is to do a level order traversal and as soon as we find a leaf node, we set the benchmark to the current level where we find the leaf node. Then we keep traversing level wise and for each leaf node found, we check whether the current traversing level is the same as the benchmark level or not. Below is the detailed implementation.

C++ Implementation

#include <bits/stdc++.h>
using namespace std;

// tree node is defined
class TreeNode {
public:
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int data)
    {
        val = data;
        left = NULL;
        right = NULL;
    }
};

void height(int level, TreeNode* root, unordered_map<TreeNode*, int>& mymap)
{
    //base case
    if (!root)
        return;

    //if current node is a leaf node
    //store it along with the current level in the hash table
    if (!root->left && !root->right) {
        mymap[root] = level;
        return;
    }

    //for the next level
    height(level + 1, root->left, mymap);
    height(level + 1, root->right, mymap);
}

bool checkAllLeavesAtSameLevel(TreeNode* root)
{
    int bench_mark = INT_MIN;
    int cur_level = 0;
 
    queue<TreeNode*> q;
 
    q.push(root);
    q.push(NULL);
 
    //while queue is not empty
    while (!q.empty()) {
        TreeNode* cur_node = q.front();
        q.pop();
        //if DeQued element is NULL
        //that means end of last level
        if (!cur_node) {
            //increment the cure=rent level
            cur_level++;
            //if queue is not empty that means there are 
            //cuurent level nodes
            if (!q.empty()) {
                //add NULL to indicqate end of current level
                q.push(NULL);
            }
        }
        else {
            //if current node is leaf node
            if (!cur_node->left && !cur_node->right) {
                //if bench mark is not set yet
                if (bench_mark == INT_MIN) {
                    //first leaf node found
                    //set the bench mark as current level

                    bench_mark = cur_level;
                }
                else {
                    //for further leaf nodes check the bench mark same 
                    //with current level or not
                    if (cur_level != bench_mark)
                        return false;
                }
            }
            if (cur_node->left)
                q.push(cur_node->left);
            if (cur_node->right)
                q.push(cur_node->right);
        }
    }

    return true;
}

int main()
{
    //building the tree like example 1
    TreeNode* root1 = new TreeNode(1);
    
    root1->left = new TreeNode(2);
    root1->right = new TreeNode(3);

    if (checkAllLeavesAtSameLevel(root1))
        cout << "Tree in example1 has all leaves at same level\n";
    else
        cout << "Tree in example1 doesn't has all leaves at same level\n";

    //building the tree-like example 2
    TreeNode* root2 = new TreeNode(1);
    
    root2->left = new TreeNode(2);
    root2->right = new TreeNode(3);
    root2->left->left = new TreeNode(4);

    if (checkAllLeavesAtSameLevel(root2))
        cout << "Tree in example2 has all leaves at same level\n";
    else
        cout << "Tree in example2 doesn't has all leaves at same level\n";
    
    return 0;
}

Output:

Tree in example1 has all leaves at same level
Tree in example2 doesn't has all leaves at same level