Closest Leaf in a Binary Tree

Medium

Databricks

18 views

Topics:

TreesGraphsRecursionDynamic Programming

Given the root of a binary tree and an integer k, you are asked to find the distance to the nearest leaf node from the node that has the value k in the tree.

Here, the distance of a leaf to a node is defined as the number of edges on the path from the node to the nearest leaf.

Return the distance to the nearest leaf node from the node that has the value k in the tree. If there is more than one node with the value k, return the minimum of these distances. If the node with the value k doesn't exist in the tree, return -1.

Example 1:

Input: root = [1,2,3,null,null,4,5,null,null,6,7], k = 2
Output: 2
Explanation: The nearest leaf node to the node with value 2 is the node with value 6. The distance is 2.

Example 2:

Input: root = [1], k = 1
Output: 0
Explanation: The nearest leaf node to the node with value 1 is the node with value 1. The distance is 0.

Example 3:

Input: root = [1,2,3,null,null,4,5,null,null,6,7], k = 5
Output: 2
Explanation: The nearest leaf node to the node with value 5 is the node with value 6. The distance is 2.

Constraints:

The number of nodes in the tree is in the range [1, 1000].
1 <= Node.val <= 1000
Each node has a unique value.
1 <= k <= 1000

Try coding it in LeetCode

Closest Leaf in a Binary Tree

Medium

Databricks

18 views

Topics:

TreesGraphsRecursionDynamic Programming

Given the root of a binary tree and an integer k, you are asked to find the distance to the nearest leaf node from the node that has the value k in the tree.

Here, the distance of a leaf to a node is defined as the number of edges on the path from the node to the nearest leaf.

Return the distance to the nearest leaf node from the node that has the value k in the tree. If there is more than one node with the value k, return the minimum of these distances. If the node with the value k doesn't exist in the tree, return -1.

Example 1:

Input: root = [1,2,3,null,null,4,5,null,null,6,7], k = 2
Output: 2
Explanation: The nearest leaf node to the node with value 2 is the node with value 6. The distance is 2.

Example 2:

Input: root = [1], k = 1
Output: 0
Explanation: The nearest leaf node to the node with value 1 is the node with value 1. The distance is 0.

Example 3:

Input: root = [1,2,3,null,null,4,5,null,null,6,7], k = 5
Output: 2
Explanation: The nearest leaf node to the node with value 5 is the node with value 6. The distance is 2.

Constraints:

The number of nodes in the tree is in the range [1, 1000].
1 <= Node.val <= 1000
Each node has a unique value.
1 <= k <= 1000

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

Can the target node be the root node itself?
What should be returned if the tree is empty, or if the target node is null?
Is the tree guaranteed to be a valid binary tree (e.g., no cycles)?
What is the data type of the node values, and can I assume they are unique?
By 'closest,' do you mean the minimum number of edges to a leaf, or do node values factor into distance (e.g., path summation)? Assume edges are the only consideration for this problem.

Brute Force Solution

Approach

The brute force approach to finding the closest leaf in a binary tree is like exploring every possible path from the target node. We will check the distance to every leaf node in the entire tree. Ultimately, we'll pick the closest one we found.

Here's how the algorithm would work step-by-step:

Start at the given node you're interested in.
Look at every single node in the entire tree, one by one.
For each of those nodes, check if it's a leaf (a node with no children).
If it is a leaf, find the distance between your starting node and that leaf node. Think of it as counting the number of steps you need to take to get from the starting node to the leaf.
Keep track of the shortest distance you've found so far to any leaf node.
After you've checked every node in the tree, the shortest distance you kept track of is the distance to the closest leaf.

Code Implementation

def find_closest_leaf_brute_force(root, target_node):
    if not root:
        return -1

    closest_distance = float('inf')

    def get_distance(node_a, node_b):
        if not node_a or not node_b:
            return float('inf')

        # Simple helper function to calculate distance between two nodes
        def find_path(start_node, end_node, current_path):
            if not start_node:
                return None
            
            current_path.append(start_node)

            if start_node == end_node:
                return current_path

            left_path = find_path(start_node.left, end_node, current_path[:])
            if left_path:
                return left_path

            right_path = find_path(start_node.right, end_node, current_path[:])
            if right_path:
                return right_path

            return None

        path = find_path(node_a, node_b, [])
        if path:
            return len(path) - 1
        else:
            return float('inf')

    def is_leaf(node):
        return node and not node.left and not node.right

    def traverse(current_node):
        nonlocal closest_distance
        if not current_node:
            return

        # Check if the current node is a leaf
        if is_leaf(current_node):
            
            # Calculate distance and update if smaller
            distance = get_distance(target_node, current_node)
            closest_distance = min(closest_distance, distance)

        traverse(current_node.left)

        traverse(current_node.right)

    # Start traversal from the root to check every node
    traverse(root)

    return closest_distance

Big(O) Analysis

Time Complexity

O(n²) – The algorithm iterates through all n nodes in the tree. For each of these nodes, it checks if the current node is a leaf. If a leaf is found, it calculates the distance to the starting node. Calculating the distance between two nodes in a tree can take O(n) time in the worst case (e.g., a skewed tree where we have to traverse almost all nodes from the start to end). Since we perform this distance calculation for each of the n nodes in the tree, the overall time complexity becomes O(n * n), which simplifies to O(n²).

Space Complexity

O(N) – The brute force approach, as described, involves exploring every node in the tree and potentially storing the distance between the starting node and each leaf. In the worst-case scenario, we might need to store distances or paths related to all N nodes of the tree. Therefore, the auxiliary space used can grow linearly with the number of nodes. This results in a space complexity of O(N).

Optimal Solution

Approach

The most efficient way to find the closest leaf to a given node in a binary tree is to combine two search strategies. We'll explore upwards from the target node while simultaneously exploring downwards from each node we reach on the upward path. This lets us quickly find leaves both near and 'above' the target node.

Here's how the algorithm would work step-by-step:

First, build a connection map that allows you to easily go from a node to its parent.
Start at the target node and search outwards towards the root of the tree.
At each node along this upward search, also start a separate search downwards to find the closest leaf in that direction.
Keep track of the shortest distance to a leaf found so far during both the upward and downward searches.
The first leaf found during downward searches on upward steps is closer than other leaf nodes.
Continue searching upwards until a leaf is found through downward search or the root node is reached.
The smallest leaf distance found in all upward or downward searches will be the answer.

Code Implementation

def find_closest_leaf(root, target):
    parent_map = {}
    def populate_parent_map(node, parent):
        if node:
            parent_map[node] = parent
            populate_parent_map(node.left, node)
            populate_parent_map(node.right, node)
    
    populate_parent_map(root, None)

    target_node = find_target_node(root, target)
    
    if not target_node:
        return None

    closest_distance = float('inf')
    closest_leaf_node = None

    visited = set()
    queue = [(target_node, 0)]
    visited.add(target_node)

    while queue:
        current_node, current_distance = queue.pop(0)
        
        # Check if the current node is a leaf.
        if not current_node.left and not current_node.right:
            if current_distance < closest_distance:
                closest_distance = current_distance
                closest_leaf_node = current_node

        # Explore downwards.
        if current_node.left and current_node.left not in visited:
            queue.append((current_node.left, current_distance + 1))
            visited.add(current_node.left)
            
        if current_node.right and current_node.right not in visited:
            queue.append((current_node.right, current_distance + 1))
            visited.add(current_node.right)

        # Explore upwards towards the root.
        parent = parent_map.get(current_node)
        if parent and parent not in visited:
            queue.append((parent, current_distance + 1))
            visited.add(parent)

    return closest_leaf_node.val

def find_target_node(root, target):
    if not root:
        return None

    if root.val == target:
        return root

    left_search = find_target_node(root.left, target)
    if left_search:
        return left_search

    return find_target_node(root.right, target)

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

Big(O) Analysis

Time Complexity

O(n) – Building the parent-node map takes O(n) time, where n is the number of nodes in the tree. The upward search from the target node can visit at most all the nodes in the path to the root, which in the worst case (a skewed tree) can be O(n). For each node visited in the upward search, a downward search for the closest leaf is performed. In the worst case, this downward search can also visit all the nodes in the subtree rooted at that node. However, since the downward searches are effectively exploring disjoint subtrees as we move upwards, the total number of nodes visited across all downward searches is bounded by n. Therefore, the overall time complexity is dominated by the initial O(n) parent map creation and the combined upward and downward traversals, resulting in O(n).

Space Complexity

O(N) – The algorithm constructs a parent map to traverse upwards; this map stores each node's parent, requiring O(N) space where N is the number of nodes in the tree. The algorithm also performs downward searches, which, in the worst-case (e.g., a skewed tree), can lead to a recursion depth of O(N). Therefore, the auxiliary space used is dominated by the parent map, resulting in O(N) space complexity.

Edge Cases

Case	How to Handle
Root is null	Return null, as there are no nodes and thus no closest leaf.
Target node is the root itself and the root is a leaf	Return the root itself immediately, as it's the closest leaf.
Tree consists of a single node which is also the target	Return the single node itself as the closest leaf.
Target node does not exist in the tree	Return null or throw an exception, indicating target node not found.
Target node is very deep within a highly unbalanced tree	Ensure the algorithm (BFS or DFS) can efficiently traverse such trees without stack overflow or excessive time complexity.
Multiple leaves are equidistant from the target node	Return any one of the closest leaves, as the problem only asks for 'a' closest leaf.
Tree with only a single branch (essentially a linked list)	Algorithm should still correctly find the closest leaf, which will be the end of the single branch.
Integer overflow during distance calculation if tree is extremely deep	Use appropriate data types (e.g., long) or carefully check for potential overflow conditions during distance calculations.