Closest leaf to root in a binary tree

Problem

Given the root of a binary tree, find the closest leaf node to the root. A leaf node is any node that does not have any children (both left and right are null).

Examples

Example 1

 Input:
          1
         / \
        2   3
           / \
          4   5
 
 Output: 2
 
 Explanation:
 Node `2` is a closest leaf to the root (distance = 1). Nodes `4` and `5` are also leaf nodes but farther (distance = 2 from root).

Example 2

 Input:
         10
        /  \
       8    12
        \
         9
 
 Output: 9
 
 Explanation:
 Node `9` is the closest leaf to root (distance = 2), whereas node `12` is farther (distance = 1 from root in different direction).

Solution

Method 1 - BFS

To solve this problem:

1. Start with the root node and traverse the tree layer by layer using Breadth First Search (BFS).
2. Leaf nodes can be identified where both left and right children are null.
3. Use BFS to guarantee the shortest distance, as BFS explores levels of the tree.

Approach

1. Use a queue to implement BFS traversal starting from the root.
2. If a node is a leaf (i.e., both children are null), return it immediately since BFS ensures the closest leaf will be found first.
3. Otherwise, enqueue the non-null children of the current node.
4. Continue traversal until a leaf node is found.

Code

Java

public class Solution {
    public int closestLeafFromRoot(TreeNode root) {
        // Edge case: Empty tree
        if (root == null) {
            return -1; // Return -1 to indicate tree does not exist
        }
        
        // BFS traversal using a queue
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        
        while (!queue.isEmpty()) {
            // Extract the current node
            TreeNode node = queue.poll();
            
            // If it's a leaf node, return its value
            if (node.left == null && node.right == null) {
                return node.val;
            }
            
            // Otherwise, enqueue its children
            if (node.left != null) {
                queue.add(node.left);
            }
            if (node.right != null) {
                queue.add(node.right);
            }
        }
        
        return -1; // This will never be reached if tree is valid
    }
}

Python

class Solution:
    def closestLeafFromRoot(self, root):
        from collections import deque

        # Edge case: Empty tree
        if not root:
            return None
        
        # BFS traversal using a queue
        queue = deque([root])
        
        while queue:
            # Extract the current node
            node = queue.popleft()
            
            # If it's a leaf node, return it
            if not node.left and not node.right:
                return node.val
            
            # Otherwise, enqueue the children
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)

Complexity

• ⏰ Time complexity: O(n). We visit each node in the tree once during BFS.
• 🧺 Space complexity: O(n). Maximum space required is proportional to the number of nodes in the largest level of the tree (in the worst case).