medium Check if all leaves are at same level

Problem Statement

Given a root of the binary tree, return true if all the leaf nodes of this tree exist at the same depth. Otherwise, return false.

Examples

Example 1:

• Input: root = [1, 2, 3, 4, null, null, 5]

• Expected Output: true
• Justification: The leaves are nodes 4 and 5, and they are both at the same level (level 3).

Example 2:

• Input: root = [12, 20, 13, null, 10, 11, null, 16]

• Expected Output: false
• Justification: The leaf node 11 is at depth 3 and leaf node 16 is at depth 4. So, both leaf nodes are at different depth.

Example 3:

• Input: root = [10, 8, 15, 17, null, 12]

• Expected Output: true
• Justification: The leaves are nodes 17, and 12, and all are located at the same level (level 3).

Solution

To solve this problem, we can use a depth-first search (DFS) traversal of the tree. DFS will allow us to explore the tree deeply, moving to the leaf nodes efficiently. During this traversal, we can keep track of the depth at which we encounter the first leaf node. As we visit each additional leaf, we compare its depth with that of the first leaf. If any leaf is found at a different depth, we know the leaves are not at the same level, and we can return false.

The advantage of DFS is that it traverses each path fully, allowing us to immediately detect depth differences without the need for additional tree traversals. This approach minimizes both time and space complexity by only requiring a single pass through the tree.

Step-by-step Algorithm

1. Initialize referenceDepth:

   • Set referenceDepth to -1. This variable will store the depth of the first leaf node we find.

2. Start DFS Traversal:

   • Begin the DFS traversal from the root of the tree, starting with depth 0.

3. Handle empty trees:

   • If the current node is null, return true. This means there’s no node to process, and we can ignore this subtree.

4. Check if the node is a leaf:

   • If the current node has no left or right children, it's a leaf node. For the first leaf node found, store its depth in referenceDepth.
   • If this is not the first leaf node, compare its depth to referenceDepth. If the depths matches, return true. Otherwise, return false.

5. Continue DFS on children:

   • If the node is not a leaf, continue DFS on its left and right children, increasing the depth by 1 each time.

6. Return the result:

   • Combine the returned value from the DFS traversal in the left and right subtree using the '&&' (and) operation, and return the final resultant boolean value.

Algorithm Walkthrough

Input: root = [1, 2, 3, 4, null, null, 5]

The binary tree looks like this:

       1
      / \
     2   3
    /     \
   4       5

We'll walk through the algorithm step by step:

1. Start DFS from root (node 1) at depth 0.

   • Node 1 is not a leaf, so we move to its left and right children.

2. DFS on left child of node 1 (node 2) at depth 1.

   • Node 2 is not a leaf, so we move to its left child.

3. DFS on left child of node 2 (node 4) at depth 2.

   • Node 4 is a leaf. Since this is the first leaf encountered, set referenceDepth = 2.

4. Backtrack to node 1 and DFS on right child of node 1 (node 3) at depth 1.

   • Node 3 is not a leaf, so we move to its right child as left child is null.

5. DFS on right child of node 3 (node 5) at depth 2.

   • Node 5 is a leaf. Compare its depth (2) with referenceDepth (2). Since they match, we continue.

6. All leaf nodes are at the same depth.

   • Both leaves (4 and 5) are at depth 2. Since no mismatch is found.

Final Output:

• The function returns true, meaning all leaf nodes are at the same level in this tree.

Code

// class TreeNode {
//     int val;
//     TreeNode left;
//     TreeNode right;

//     // Constructor to initialize the node with children
//     TreeNode(int val, TreeNode left, TreeNode right) {
//         this.val = val;
//         this.left = left;
//         this.right = right;
//     }
// }

class Solution {

  int referenceDepth = -1; // Variable to store the depth of the first leaf node encountered

  // Method to check if all leaf nodes are at the same level
  public boolean checkLeaves(TreeNode root) {
    return dfs(root, 0); // Start DFS traversal from the root with depth 0
  }

  // Helper method for DFS traversal
  private boolean dfs(TreeNode node, int depth) {
    if (node == null) { // If the node is null, it's an empty subtree
      return true;
    }

    // Check if it's a leaf node (no left and right children)
    if (node.left == null && node.right == null) {
      if (referenceDepth == -1) { // If this is the first leaf node, store its depth
        referenceDepth = depth;
      }
      return depth == referenceDepth; // Compare current leaf's depth with reference depth
    }

    // Continue DFS traversal for left and right children
    return dfs(node.left, depth + 1) && dfs(node.right, depth + 1);
  }

  // Main method to test the solution
  public static void main(String[] args) {
    // Create the tree [1, 2, 3, 4, null, null, 5]

    // Root node
    TreeNode root = new TreeNode(1);

    // Left subtree
    root.left = new TreeNode(2);
    root.left.left = new TreeNode(4); // Leaf node at level 3

    // Right subtree
    root.right = new TreeNode(3);
    root.right.right = new TreeNode(5); // Leaf node at level 3

    // Create an instance of Solution and call the checkLeaves method
    Solution solution = new Solution();
    boolean result = solution.checkLeaves(root); // Call method to check if leaves are at same level

    // Output the result
    System.out.println(result); // Expected output: true
  }
}

Complexity Analysis

Time Complexity

The time complexity of the algorithm is , where n is the number of nodes in the binary tree. This is because the DFS traversal visits every node exactly once.

Space Complexity

The space complexity is , where h is the height of the binary tree. This comes from the recursion stack used by the DFS traversal. In the worst case (a skewed tree), the recursion depth can be equal to the total number of nodes in the tree and the overall space complexity can be .