Closest Leaf In A Binary Tree - Leetcode Solution

Closest Leaf In A Binary Tree is a problem on Leetcode which requires finding the closest leaf node from a given target node in a binary tree. The solution to this problem involves traversing the binary tree and finding the distance between the target node and the leaf nodes. The node with the minimum distance is the closest leaf node.

To solve this problem, we can use a depth-first search (DFS) algorithm to traverse the binary tree. The algorithm takes the target node as the input and finds the closest leaf node. Here are the steps to solve the Closest Leaf In A Binary Tree problem:

1. Create a hashmap to store the parent node of each node in the binary tree.
2. Traverse the binary tree and fill the hashmap by storing the parent node of each node in the tree.
3. Start from the target node and traverse the tree to find the distance between the target node and each leaf node.
4. Store the minimum distance found during step 3 and the corresponding leaf node.
5. Return the leaf node with the minimum distance.

The time complexity of this algorithm is O(n), where n is the number of nodes in the binary tree.

Here is a sample code for the Closest Leaf In A Binary Tree problem in Python:

class Solution:
    def findClosestLeaf(self, root: TreeNode, k: int) -> int:
        
        # TreeNode class definition
        class TreeNode:
            def __init__(self, x):
                self.val = x
                self.left = None
                self.right = None
                
        # Helper function to traverse the tree
        def dfs(node, parent_map, target):
            if not node:
                return None
            if node.val == target:
                return node
            if node.left:
                parent_map[node.left] = node
                left_res = dfs(node.left, parent_map, target)
                if left_res:
                    return left_res
            if node.right:
                parent_map[node.right] = node
                right_res = dfs(node.right, parent_map, target)
                if right_res:
                    return right_res
            return None
        
        # Traverse the tree and fill the parent hashmap
        parent_map = {}
        dfs(root, parent_map, k)
        
        # Traverse the tree again to find the closest leaf node
        target_node = dfs(root, parent_map, k)
        visited = set()
        min_distance = float('inf')
        min_leaf = None
        
        def dfs_min_distance(node, distance):
            nonlocal visited, min_distance, min_leaf
            
            # Base case
            if not node:
                return
            
            # If we reach a leaf node, check if it is the closest leaf node
            if not node.left and not node.right:
                if distance < min_distance:
                    min_distance = distance
                    min_leaf = node.val
            
            # Visit left and right nodes
            if node.left and node.left not in visited:
                visited.add(node.left)
                dfs_min_distance(node.left, distance+1)
            if node.right and node.right not in visited:
                visited.add(node.right)
                dfs_min_distance(node.right, distance+1)
                
            # Visit parent node
            if node in parent_map and parent_map[node] not in visited:
                visited.add(parent_map[node])
                dfs_min_distance(parent_map[node], distance+1)
                
        dfs_min_distance(target_node, 0)
        return min_leaf

This solution will return the value of the closest leaf node from the given target node in the binary tree.

1