Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
1.1.
Problem Statement
1.2.
Sample Example
2.
Brute Force Approach
2.1.
PseudoCode
2.2.
Implementation in C++
2.2.1.
Complexity Analysis
3.
Optimized Approach
3.1.
PseudoCode
3.2.
Implementation in C++
3.2.1.
Complexity Analysis
4.
Frequently Asked Questions
4.1.
What is the time complexity of insertion in a Binary Tree?
4.2.
What is the time complexity of deletion inside a BST?
4.3.
Name any three order traversals of a binary tree?
5.
Conclusion
Last Updated: Mar 27, 2024

Check if all leaves are at the same level

Author aniket verma
0 upvote
Crack Google SDE interview : Essential projects
Speaker
Saurav Prateek
SDE-2 @
20 Jun, 2024 @ 01:30 PM

Introduction

In this blog, we will discuss how to Check if all leaves are at the same level. Such problems are fairly common interview questions as well asked in many contests. Before solving the problem, it’s recommended to have a good understanding of binary trees. In this Blog we will dive deep into each detail to get a firm hold over how we can reach from a brute force solution to an optimal solution .  

Problem Statement

Given a root to a binary tree. Check if all leaves are at the same level. Return true if all leaves are at the same level. Otherwise return False.

Sample Example

Input:  

 

Output True

Explanation: All the leaves in the binary tree given above are at the same level - 2(taking root to be at level 0).

Brute Force Approach

First, let’s look at the naive approach that would probably strike anybody’s mind before jumping to an optimal approach. We need to Check if all leaves are at the same level.

So, the basic approach is to store the level of each leaf node and compare if all levels are equal or not.

So the naive/basic approach could be formulated as:

  1. Find the level of each binary tree leaf node and store them in a map.
  2. Check if all the levels stored in the map are equal or not.
  3. Return True in case levels are the same .
  4. Otherwise return False.

 

NOTE: we could store the levels either iteratively via a simple BFS or using a DFS Algorithm traversal on the binary tree also.

Now let’s look at the PseudoCode.

PseudoCode

Algorithm

___________________________________________________________________

procedure computeLeafNodeLevels(rootNode, level, leafNodeLevels):

___________________________________________________________________

1.    if rootNode is NIL do 

2.         return 

3.    else if isLeafNode(rootNode) is True  do

4.      leafNodeLevels[rootNode] ← level

5.          return

6.    else do

7.          computeLeafNodeLevels(rootNode.left, level+1, leafNodeLevels)

8.          computeLeafNodeLevels(rootNode.left, level+1, leafNodeLevels)

9.    end if

10. end procedure

___________________________________________________________________

procedure checkAllLeavesAtSameLevel(rootNode):

___________________________________________________________________

1.    leafNodeLevels ← map to store the level of all leaf nodes. 

2.    computeLeafNodeLevels(rootNode, 0, leafNodelevels)

3.    initialLeafLevel ← initialised to any value from leafNodelevel map

4.   for each node, level in leafNodeLevels do

5.          if initialLeafLevel != level do 

6.                return False

7.          end if

8.    end if

9.   return True

10. end procedure

___________________________________________________________________

Implementation in C++

// program to check if all leaves are at the same level
#include <bits/stdc++.h>
#define Node struct BinaryTreeNode
using namespace std;


// binary tree node
struct BinaryTreeNode{
    int val;
    BinaryTreeNode* left; 
    BinaryTreeNode* right;
    BinaryTreeNode(int nodeValue){
        val = nodeValue;
        left = nullptr;
        right = nullptr;
    }
};


// check if a node is a leaf node or not
bool isLeafNode(Node* node){
    return !node->left and !node->right;
}


// compute all leaf node levels
void computeLeafNodeLevels(Node* rootNode, int level, map<Node*, int> &leafNodeLevels){
    
    // if rootNode is null return
    if(rootNode==nullptr){ 
        return; 
    }
    
    // if it's a leaf node store its level
    else if(isLeafNode(rootNode)){
        leafNodeLevels[rootNode] = level;
        return;
    }


    //compute leaf node levels on both left and right subtrees
    else{
        computeLeafNodeLevels(rootNode->left, level+1, leafNodeLevels);
        computeLeafNodeLevels(rootNode->right, level+1, leafNodeLevels);
    }
}



// function to check All Leaves are at the SameLevel
bool checkAllLeavesAtSameLevel(Node* rootNode){
    map<Node*, int> leafNodeLevels; // map containing levels of all leaf Nodes
    
    computeLeafNodeLevels(rootNode, 0, leafNodeLevels); // compute all leaf node levels
    
    int initialLeafLevel = (*leafNodeLevels.begin()).second; //store the initialLeafLevel
    
    for(auto it = leafNodeLevels.begin(); it!=leafNodeLevels.end(); ++it){
        int level = (*it).second; // level of the leaf node
        if(initialLeafLevel != level){
            return false; // return false if not same
        }
    }
    
    return true; // return true since all levels are same
}


int main() {
    
    // create the sample binary tree here 
	Node* root = new Node(1);
	root->left = new Node(2);
	root->right = new Node(3);
	root->left->left = new Node(4);
	root->right->right = new Node(5);

	// find whether all the leaves are at the same level or Not
	cout<<(checkAllLeavesAtSameLevel(root)?"True":"False")<<'\n';
	return 0;
}

 

Output:

True

 

Complexity Analysis

Time Complexity: O(nlogn)

This is because we iterate through the entire binary tree once to store the levels of all leaf nodes. But since the map is being used and takes O(logn) time in the worst case. Hence the time complexity.

Space complexity: O(n) at the worst case because we are storing the levels of all leaf nodes and the recursion stack being used.

The above algorithm works in O(nlogn) time. Can we improve our solution in terms of both space and time??

So let’s think about an efficient approach to solve the problem.

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

Optimized Approach

If we want to build up an efficient solution, we will need to find out if there is any redundancy or any repetition that we are doing.

If we carefully notice the extra computation being done in our approach above, we could observe that we are storing the levels of all leaf nodes in a map. But do we actually need a map?? 

No, because we can easily store it in a vector or an array and iterate through it which would reduce our time complexity to O(n) definitely. But our task is to optimise the solution as much as possible. So we are already using the recursion stack, do we actually need to store the levels??

 

Let’s see how we can eliminate the use of the levels we are storing.

Let’s say we have ‘k’ leaf nodes. Now let the levels stored be  l1, l2 … lk .

So if all the levels will be the same then l1 = l2 = l3 …. = lk  must be true. 

 

Let’s assume that all the leaves are not at the same level. Then even one differing level would suffice. Say the jth leaf node level lj  is different from others. So checking lj-1 and lj  or lj and lj+1 would be sufficient to say they are not equal. If we don’t find such a case then we can easily say that all levels are at the same level. In other words we can say that we just need the previous leaf node level to check this condition.

Now having said that, what we can do is store the initial level as the value of the first leaf node level and compare it while iterating over the other leaf nodes using recursion itself in the same way as done in the brute force approach.

Now we can formulate our approach:

  1. Traverse the Leaf nodes and maintain the initial level to keep track of previous node’s level .
  2. If the previous node level is not equal to the current node level, we can return false right away.
  3. If such a case is not found, return true.

 

Let’s look at the pseudoCode

PseudoCode

Algorithm

___________________________________________________________________

procedure checkAllLeavesAtSameLevel(rootNode, level, prevLeafLevel):

___________________________________________________________________

1.    if rootNode is NIL do

2.         return True

3.   else if isLeafNode(rootNode) do

4.          if isUpdated(prevLeafLevel) and level != prevLeafLevel do

5.               return False

6.          else do

7.               prevLeafLevel ← level

8.               return True

9.          end if

10.   else do

11.       return checkAllLeavesAtSameLevel(rootNode.left, level + 1, prevLeafLevel)

12.          and checkAllLeavesAtSameLevel(rootNode.right, level + 1, prevLeafLevel) 

10. end procedure

___________________________________________________________________

Implementation in C++

// program to check if all leaves are at the same level
#include <bits/stdc++.h>
#define Node struct BinaryTreeNode
using namespace std;


// binary tree node
struct BinaryTreeNode{
    int val;
    BinaryTreeNode* left; 
    BinaryTreeNode* right;
    BinaryTreeNode(int nodeValue){
        val = nodeValue;
        left = nullptr;
        right = nullptr;
    }
};


// check if a node is a leaf node or not
bool isLeafNode(Node* node){
    return !node->left and !node->right;
}


// function to check All Leaves are at the SameLevel
bool checkAllLeavesAtSameLevel(Node* rootNode, int level, int &prevLeafLevel){
    
    // if rootNode is null return
    if(rootNode==nullptr){ 
        return true; 
    }
    
    
    // if it's a leaf node check the condition
    else if(isLeafNode(rootNode)){
        if(prevLeafLevel!=INT_MAX and prevLeafLevel!=level){
            return false;
        } else{
            prevLeafLevel = level;
            return true;
        }
    }

    //compute results for both left and right subtress
    else{
        return checkAllLeavesAtSameLevel(rootNode->left, level+1, prevLeafLevel) and
        checkAllLeavesAtSameLevel(rootNode->right, level+1, prevLeafLevel);
    }
}



int main() {
    
    // create the sample binary tree here 
	Node* root = new Node(1);
	root->left = new Node(2);
	root->right = new Node(3);
	root->left->left = new Node(4);
	root->right->right = new Node(5);

	int prevLeafLevel = INT_MAX;

	// find whether all the leaves are at the same level or Not
	cout<<(checkAllLeavesAtSameLevel(root, 0, prevLeafLevel)?"True":"False")<<'\n';
	return 0;
}

 

Output:

True

 

Complexity Analysis

Time Complexity: O(n)

We are simply iterating the binary tree only once. Hence, O(n) where n is the number of nodes.

Space complexity: O(n) at the worst case, as we are using an auxiliary stack.  

Thus we have reached an optimal solution to check if all leaves are at the same level.

Frequently Asked Questions

What is the time complexity of insertion in a Binary Tree?

The time complexity of insertion inside a binary tree is O(n). 

What is the time complexity of deletion inside a BST?

The time complexity of insertion inside a binary search tree is O(n). 

Name any three order traversals of a binary tree?

PostOrder, PreOrder, InOrder are three most common ordered traversals of a binary tree.

Conclusion

This article taught us how to solve the problem check if all leaves are at the same level. We also saw how to approach the problem using a naive approach followed by an efficient solution. We discussed a recursive implementation using examples, pseudocode, and proper code in detail.

Check out this problem - Root To Leaf Path

Refer to our Guided Path on Coding Ninjas Studio to upskill yourself in Data Structures and AlgorithmsCompetitive ProgrammingJavaScriptSystem DesignMachine learning and many more! If you want to test your competency in coding, you may check out the mock test series and participate in the contests hosted on Coding Ninjas Studio! But if you have just started your learning process and are looking for questions asked by tech giants like Amazon, Microsoft, Uber, etc; you must look at the problemsinterview experiences, and interview bundle for placement preparations.

Nevertheless, you may consider our paid courses to give your career an edge over others!

Do upvote our blogs if you find them helpful and engaging!

Happy Learning!!

Previous article
Check for Children Sum Property in a Binary Tree
Next article
Check if a given binary tree is a subtree of another binary tree or not
Live masterclass