Skip to main content

Check if all leaves are at same level

The problem are involves checking whether all the leaves of a binary tree are at the same level or not. In a binary tree, leaves are nodes that do not have any children. The goal is to determine if all the leaf nodes in the tree are present at the same depth or level.

Problem Statement and Description

Given a binary tree, the task is to write a program that checks whether all the leaf nodes in the tree are at the same level or not. If all the leaf nodes are at the same level, the program should output "Yes," otherwise, it should output "No."

Example

Consider the following binary tree:

      1
    /   \
   2     3
  /     / \
 4     5   6

In this tree, all the leaf nodes (4, 5, and 6) are at the same level, so the program should output "Yes."

If we add another leaf node, the tree becomes:

       1
     /   \
    2     3
   /     / \
  4     5   6
 /
7

In this modified tree, the leaf nodes (4, 5, 6, and 7) are not at the same level, so the program should output "No."

Idea to Solve the Problem

Check if all leaves are at same level

To solve this problem, we can follow these steps:

  1. Traverse the binary tree and identify all the leaf nodes.
  2. During traversal, keep track of the level at which each leaf node is found.
  3. If all the leaf nodes are at the same level, the level value for each leaf node will be the same.
  4. If there are leaf nodes at different levels, the level values will be different.

Standard Pseudocode

Here's a high-level pseudocode representation of the algorithm to check if all leaves are at the same level:


CheckLeafLevel(node, level):
    if node is NULL:
        return
    
    if node is a leaf:
        if level is not initialized:
            initialize level with current level
        else if level is different from current level:
            set level to -1
            return
    else:
        CheckLeafLevel(node.left, level + 1)
        CheckLeafLevel(node.right, level + 1)

Algorithm Explanation

  1. Traverse the binary tree in a recursive manner.
  2. For each node, if it is a leaf node:
    • If the level variable is not initialized, set it to the current level.
    • If the level variable is already initialized and is different from the current level, set level to -1, indicating that leaf nodes are not at the same level.
  3. If the current node is not a leaf node, recursively visit its left and right subtrees, increasing the level value by 1.

Code solution

Time Complexity

The time complexity of the provided code mainly depends on the traversal of the binary tree. In the worst case, the algorithm visits every node once, resulting in a time complexity of O(n), where 'n' is the number of nodes in the tree.





Comment

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.

New Comment