Leaves at Same Level

Given a binary tree with n nodes, determine whether all the leaf nodes are at the same level or not. Return true if all leaf nodes are at the same level, and false otherwise.

?? View Full Code ??

Approach :

• Recursive Traversal: Perform a depth-first traversal of the binary tree.
• Track Leaf Level: For each leaf node, record its level. If it’s the first leaf node encountered, set this level as the reference level.
• Compare Levels: For each subsequent leaf node, compare its level to the reference level. If they don’t match, set an indicator to false and stop further checks.
• Return Result: If all leaf nodes are found at the same level, return true. Otherwise, return false.

void solve(Node* root, int height, int &ans, int &lvl){
        
        if(root == NULL) return;
        
        if(ans == 0) return;
        
        if(root->left == NULL && root->right == NULL){
            if(lvl == -1){
                lvl = height;
            }
            else{
                if(height != lvl){
                    ans = 0;
                }
                
            }
        }
        
        solve(root->left, height+1, ans, lvl);
        solve(root->right, height+1, ans, lvl);
    }
    bool check(Node *root)
    {
        int height = 0;
        int ans = 1;
        int lvl = -1;
        
        solve(root, height, ans, lvl);
        
        return ans;
    }        

Explanation :

• Function solve: This is a helper function that performs the actual traversal. height is the current depth in the tree. ans tracks whether all leaves are at the same level (1 for true, 0 for false). lvl stores the level of the first leaf node encountered.
• Leaf Check: If the node has no left or right child, it’s a leaf node. If this is the first leaf (indicated by lvl == -1), store its level in lvl. For subsequent leaves, if their level does not match lvl, set ans to 0 and stop further processing.
• Function check: This initializes variables and calls solve to begin the recursive traversal.

?? GitHub Repo ??

Time Complexity : O(N)

Time Complexity : O(H)

N is number of nodes, H is height of tree.