C++ program to Check if all leaves are at same level

A node of a tree is called leaf when it’s both the children are NULL. Now, in a given binary tree, we have to check whether all the leaves are at the same level.

Check_leaf_at_same_levels_2

In this tree, all the blue nodes are leaf nodes. Here, they are not at the same level so it will result in false.

Check_leaf_at_same_levels_1

In this tree, all the blue nodes are leaf nodes. Here, they all are at the same level so it will result in true.

Method 1 (Using DFS)

Approach:

      We have to traverse all the nodes to check the leaves. We will use only one traversal to solve the problem. This one is a tricky implementation of “getting the height of a binary tree problem”.

      In this approach, we will handle the return value very smartly. Return value -1 means all the leaves are not at the same level. Any values other than -1 says two things, it says that all the leaves are at the same level and the value represents the height at which all the leaves are present (i.e. the height of the tree). 

How this works:

      Leaves will return height as 1. For the nodes having only one child, we will go for recursion call only for that child. For others, we will go forward recursively for the left subtree as well as the right subtree. Suppose, any of the left or right subtree is not having all the leaves at the same level, then the overall tree is also not having all the leaves at the same level. So, if any of the left or right subtree recursion call returns -1 (i.e. not having all the leaves at the same level), it will also return -1.

      In another case, suppose left and right subtree both have all the leaves at the same level but the heights of them are not the same, then also the overall tree is not having all leaves at the same level. So, if the left and right subtree recursion calls return a value other than -1 but they are not the same, it will also return -1. Now for the last case, if the left and right subtree recursion calls return a value other than -1 and they are the same, it returns left height (or, right height) + 1 (to return the height).

      Finally, if we get -1 as the return value it means not all the leaves are at the same level. Otherwise, all of them are on the same level.

Code:

#include <iostream>
using namespace std;

// Structure to represent every node of tree
struct Node{
    int data;
    Node* left;
    Node* right;
};

// Function to allocate new node.
Node* newNode(int val) {
    Node* temp = new Node();

    temp->data = val;
    temp->left = NULL;
    temp->right = NULL;

    return temp;
}

int traverse(Node* root) {

    // If node is leaf node then returns height as 1
    if(root->left == NULL && root->right == NULL)
        return 1;
    
    // If both children are not NULL
    // it checks for left and right recursively    
    if(root->left && root->right) {
        int l = traverse(root->left);
        int r = traverse(root->right);
        
        if(l == -1 || r == -1 || l != r)
            return -1;
            
        return l+1;
    }
    
    // This part checks for the child which is not NULL
    int rel;
    
    if(root->left) {
        rel = traverse(root->left);
    }
    
    if(root->right) {
        rel = traverse(root->right);
    }
    
    if(rel != -1)
        rel++;
    
    return rel;
}

bool atSameLevel(Node* root) {
    // If root is NULL then the tree is empty
    // so the condition satisfies.
    if(root == NULL)
        return true;

    if(traverse(root) == -1)
        return false;

    return true;
}

int main() {
    Node* root;

    // Sample tree.
    root = newNode(3);
    root->left = newNode(5);
    root->right = newNode(4);
    root->right->left = newNode(7);
    root->right->right = newNode(1);

    if(atSameLevel(root))
        cout << "YES\n";
    else
        cout << "NO\n";

    return 0;
}

Output:

NO

Complexity analysis:

  • Time Complexity:  O(N), where N is the number of nodes. As we have to traverse through all the nodes, the time complexity will be O(N).
  • Space Complexity:  O(H), where H is the height of the binary tree. As we proceed through recursion, there will be a maximum of H items in the recursion call stack. So, space complexity is O(H).

Method 2 (Using BFS)

Approach:

In this approach, we will use the concept of level order traversal line by line. In level order traversal we use a queue to store the nodes, here we proceed in a similar manner. Suppose, we get a leaf at a certain level, and after the traversal of that level if we have any node in the queue that means there is at least one leaf node in the next levels. If this case arises, we can say that all the leaves are not at the same level. Otherwise, all of them are on the same level. Let’s jump into the code.

Code:

#include <iostream>
#include <queue>
using namespace std;

// Structure to represent every node of tree
struct Node{
    int data;
    Node* left;
    Node* right;
};

// Function to allocate new node.
Node* newNode(int val) {
    Node* temp = new Node();
    temp->data = val;
    temp->left = NULL;
    temp->right = NULL;
    return temp;
}

bool atSameLevel(Node* root) {
    // If root is NULL then the tree is empty
    // so the condition satisfies.
    if(root == NULL)
        return true;
    
    // Count for leaves
    int count = 0;

    Node *temp;
    queue<Node*> q;

    q.push(root);

    while(!q.empty()) {

        // If we got leaf and queue is not empty
        // means not all leaves at same level.
        if(count > 0)
            return false;

        int len = q.size();

        for(int i=0; i<len; i++) {
            temp = q.front();
            q.pop();

            // Checking for leaf
            if(temp->left == NULL && temp->right == NULL)
                count++;
            
            // Pushing the children in queue
            else{
                if(temp->left)
                    q.push(temp->left);
                if(temp->right)
                    q.push(temp->right);
            }
        }
    }

    return true;
}

int main() {
    Node* root;
    // Sample tree.
    root = newNode(3);
    root->left = newNode(5);
    root->right = newNode(4);
    root->left->left = newNode(2);
    root->left->right = newNode(6);
    root->right->left = newNode(7);
    root->right->right = newNode(1);

    if(atSameLevel(root))
        cout << "YES\n";
    else
        cout << "NO\n";

    return 0;
}

Output:

YES

Complexity analysis:

  • Time Complexity:  O(N), where N is the number of nodes. As we have to traverse through all the levels in the worst case, the time complexity will be O(N).
  • Space Complexity:  O(W), where W is the width of the binary tree.

Leave a Reply

Your email address will not be published. Required fields are marked *