Problem Statement

Given a Binary Tree, check if all leaves are at same level or not.

Example 1:

Input:
            1
          /   \\
         2     3

Output: 1

Explanation:
Leaves 2 and 3 are at same level.

Example 2:

Input:
            10
          /    \\
        20      30
       /  \\
     10    15

Output: 0

Explanation:
Leaves 10, 15 and 30 are not at same level.

Approach

The idea is to iteratively traverse the tree, and when you encounter the first leaf node, store it’s level in result variable, now whenever you encounter any leaf node, compare it’s level with previously stored result, it they are same then proceed for rest of the tree, else return false.

Problem Link

Check if all leaves are at same level - GeeksforGeeks

Code

/* The structure of the binary tree is as follows
struct Node
{
    int data;
    Node* left;
    Node* right;
};
*/

class Solution{
  public:
    /*You are required to complete this method*/
    bool check(Node *root)
    {
        if(!root)
        return true;
        
        queue<Node*> q;
        
        q.push(root);
        int depth = 0, res = -1;
        
        while(!q.empty())
        {
            int lsize = q.size();
            
            
            
            while(lsize--)
            {
                Node *curr = q.front();
                q.pop();
                
                if(curr->left)
                {
                    q.push(curr->left);
                    
                    // if it's leaf node
                    if(!curr->left->left&&!curr->left->right)
                    {
                        // if it's first leaf node till now,
                        // then update the result
                        if(res==-1)
                        res = depth;
                        
                        // if it is not the first leaf node,
                        // then compare the level with level
                        // of previous leaf node
                        else if(res!=depth)
                        return false;
                    }
                }
                
                if(curr->right)
                {
                    q.push(curr->right);
                    
                    // if it's leaf node
                    if(!curr->right->left&&!curr->right->right)
                    {
                        
                        // if it's first leaf node till now,
                        // then update the result
                        if(res==-1)
                        res = depth;
                        
                        // if it is not the first leaf node,
                        // then compare the level with level
                        // of previous leaf node
                        else if(res!=depth)
                        return false;
                    }
                    
                }
            }
            depth++;
            
            
            
        }
        return true;
    }
};