Closest Leaf in a Binary Tree

2 min readUpdated 15 May 2025

Problem Statement

The task is to find the value of the nearest leaf node in a binary tree relative to a node with a specified value k. In a binary tree where each node holds a unique value, a node is referred to as a leaf if it does not have any children nodes. The proximity is defined by the minimal number of edges between the node k and any leaf node.

Examples

Example 1

Input:

EXAMPLE_ENTITY

root = [1,3,2], k = 1

Output:

EXAMPLE_ENTITY

Explanation:

EXAMPLE_ENTITY

Either 2 or 3 is the nearest leaf node to the target of 1.

Example 2

Input:

EXAMPLE_ENTITY

root = [1], k = 1

Output:

EXAMPLE_ENTITY

Explanation:

EXAMPLE_ENTITY

The nearest leaf node is the root node itself.

Example 3

Input:

EXAMPLE_ENTITY

root = [1,2,3,4,null,null,null,5,null,6], k = 2

Output:

EXAMPLE_ENTITY

Explanation:

EXAMPLE_ENTITY

The leaf node with value 3 (and not the leaf node with value 6) is nearest to the node with value 2.

Constraints

The number of nodes in the tree is in the range [1, 1000].
1 <= Node.val <= 1000
All the values of the tree are unique.
There exist some node in the tree where Node.val == k.

Approach and Intuition

To solve this problem, one must understand the navigation through a binary tree and the properties of leaf nodes. Here’s a stepwise approach based on the example situations provided:

The first task is to locate the node in the tree that contains the target value k.
Once the target node is located, determine the nearest leaf node. This involves evaluating the shortest path from the target node to any reachable leaf node.
Consider both child nodes and possibly tracing back up through parent nodes to find all possible paths to leaf nodes.

Observations:

If the target node k itself is a leaf node, that is the nearest by default.
In more complex tree structures, consider both children and parent paths, calculating the minimal number of edges from the target node k to any leaf node.

This generalized approach essentially covers navigation within the tree, either branching out from the target to trace all possible paths to leaf nodes or, in simpler cases, acknowledging the target itself as the nearest leaf when applicable. Each node must be checked minimally, involving either direct downward traversal towards children or an upward-backtracking to capture all potential candidates for nearest leaf nodes.

Solutions

JAVA
class Solution {
    List<TreeNode> searchPath;
    Map<TreeNode, LeafResult> memoization;
    
    public int findClosestLeaf(TreeNode root, int k) {
        searchPath = new ArrayList<>();
        memoization = new HashMap<>();
    
        exploreTree(root, k);
    
        int stepsFromK = searchPath.size() - 1;
        int minDistance = Integer.MAX_VALUE;
        TreeNode nearestLeaf = null;
        for (TreeNode currentNode: searchPath) {
            LeafResult closest = getClosestLeaf(currentNode);
            int currentDistance = closest.dist + stepsFromK;
            if (currentDistance < minDistance) {
                minDistance = currentDistance;
                nearestLeaf = closest.node;
            }
            stepsFromK--;
        }
        return nearestLeaf.val;
    }
    
    public boolean exploreTree(TreeNode node, int k) {
        if (node == null) {
            return false;
        } else if (node.val == k) {
            searchPath.add(node);
            return true;
        } else {
            searchPath.add(node);
            boolean found = exploreTree(node.left, k);
            if (found) {
                return true;
            }
            found = exploreTree(node.right, k);
            if (found) {
                return true;
            }
            searchPath.remove(searchPath.size() - 1);
            return false;
        }
    }
    
    public LeafResult getClosestLeaf(TreeNode root) {
        if (root == null) {
            return new LeafResult(null, Integer.MAX_VALUE);
        } else if (root.left == null && root.right == null) {
            return new LeafResult(root, 0);
        } else if (memoization.containsKey(root)) {
            return memoization.get(root);
        } else {
            LeafResult leftResult = getClosestLeaf(root.left);
            LeafResult rightResult = getClosestLeaf(root.right);
            LeafResult finalResult = new LeafResult(leftResult.dist < rightResult.dist ? leftResult.node : rightResult.node,
                                            Math.min(leftResult.dist, rightResult.dist) + 1);
            memoization.put(root, finalResult);
            return finalResult;
        }
    }
}
class LeafResult {
    TreeNode node;
    int dist;
    LeafResult(TreeNode n, int d) {
        node = n;
        dist = d;
    }
}
Powered by Vultr AgentBeta

Based on the Java code provided for finding the closest leaf to a given node in a binary tree, the code effectively utilizes several advanced programming concepts and data structures including recursion, memoization, and depth-first search (DFS).

Here's a concise description of how the solution operates:

Initialization: Two data structures, searchPath (a list) and memoization (a map), are initialized. searchPath captures the path from the root to the target node k, and memoization stores the results of subproblems to avoid redundant calculations.
Tree Exploration: The method exploreTree navigates through the binary tree recursively. It builds the path from the root to the node containing the integer k. If k is located, the reverse path building stops, and the method returns true, indicating k has been located.
Finding the Nearest Leaf: Once the path to k is identified, the method findClosestLeaf evaluates each node in this path for its proximity to the nearest leaf. It computes the distance from each node to its nearest leaf, which is minimized using the helper method getClosestLeaf.
Leaf Distance Calculation: The utility function getClosestLeaf calculates the nearest leaf for a given node using both its child nodes, considering previously computed results stored in memoization for optimization. This method recursively determines the least distance of the leaves from each subtree, adjusting the current node's leaf distance accordingly. If a node is a leaf (i.e., has no children), it directly returns itself with a distance of zero.
Output: The final result returned by the method findClosestLeaf is the value of the nearest leaf node.

Overall, this code efficiently combines memoization with depth-first traversal to optimize the search process in a binary tree, focusing on achieving minimal computational complexity by caching intermediate results and avoiding revisiting nodes unnecessarily.

More to Explore

Tech Talk: Running a Self-Improving AI Agent with Hermes on Vultr

Tech Talk: Implementing Fine-Grained Access Control with Vultr IAM

Tech Talk: Getting Started with Vultr IAM

Tech Talk: Simplifying Zero-Trust Networking with NetBird on Vultr Marketplace

0 Comments

Start the conversation

Be the first to comment and share your perspective with the community.

Closest Leaf in a Binary Tree

2 min readUpdated 15 May 2025

Problem Statement

Examples

Example 1

Input:

EXAMPLE_ENTITY

root = [1,3,2], k = 1

Output:

EXAMPLE_ENTITY

Explanation:

EXAMPLE_ENTITY

Either 2 or 3 is the nearest leaf node to the target of 1.

Example 2

Input:

EXAMPLE_ENTITY

root = [1], k = 1

Output:

EXAMPLE_ENTITY

Explanation:

EXAMPLE_ENTITY

The nearest leaf node is the root node itself.

Example 3

Input:

EXAMPLE_ENTITY

root = [1,2,3,4,null,null,null,5,null,6], k = 2

Output:

EXAMPLE_ENTITY

Explanation:

EXAMPLE_ENTITY

The leaf node with value 3 (and not the leaf node with value 6) is nearest to the node with value 2.

Constraints

The number of nodes in the tree is in the range [1, 1000].
1 <= Node.val <= 1000
All the values of the tree are unique.
There exist some node in the tree where Node.val == k.

Approach and Intuition

To solve this problem, one must understand the navigation through a binary tree and the properties of leaf nodes. Here’s a stepwise approach based on the example situations provided:

The first task is to locate the node in the tree that contains the target value k.
Once the target node is located, determine the nearest leaf node. This involves evaluating the shortest path from the target node to any reachable leaf node.
Consider both child nodes and possibly tracing back up through parent nodes to find all possible paths to leaf nodes.

Observations:

If the target node k itself is a leaf node, that is the nearest by default.
In more complex tree structures, consider both children and parent paths, calculating the minimal number of edges from the target node k to any leaf node.

Solutions

JAVA
class Solution {
    List<TreeNode> searchPath;
    Map<TreeNode, LeafResult> memoization;
    
    public int findClosestLeaf(TreeNode root, int k) {
        searchPath = new ArrayList<>();
        memoization = new HashMap<>();
    
        exploreTree(root, k);
    
        int stepsFromK = searchPath.size() - 1;
        int minDistance = Integer.MAX_VALUE;
        TreeNode nearestLeaf = null;
        for (TreeNode currentNode: searchPath) {
            LeafResult closest = getClosestLeaf(currentNode);
            int currentDistance = closest.dist + stepsFromK;
            if (currentDistance < minDistance) {
                minDistance = currentDistance;
                nearestLeaf = closest.node;
            }
            stepsFromK--;
        }
        return nearestLeaf.val;
    }
    
    public boolean exploreTree(TreeNode node, int k) {
        if (node == null) {
            return false;
        } else if (node.val == k) {
            searchPath.add(node);
            return true;
        } else {
            searchPath.add(node);
            boolean found = exploreTree(node.left, k);
            if (found) {
                return true;
            }
            found = exploreTree(node.right, k);
            if (found) {
                return true;
            }
            searchPath.remove(searchPath.size() - 1);
            return false;
        }
    }
    
    public LeafResult getClosestLeaf(TreeNode root) {
        if (root == null) {
            return new LeafResult(null, Integer.MAX_VALUE);
        } else if (root.left == null && root.right == null) {
            return new LeafResult(root, 0);
        } else if (memoization.containsKey(root)) {
            return memoization.get(root);
        } else {
            LeafResult leftResult = getClosestLeaf(root.left);
            LeafResult rightResult = getClosestLeaf(root.right);
            LeafResult finalResult = new LeafResult(leftResult.dist < rightResult.dist ? leftResult.node : rightResult.node,
                                            Math.min(leftResult.dist, rightResult.dist) + 1);
            memoization.put(root, finalResult);
            return finalResult;
        }
    }
}
class LeafResult {
    TreeNode node;
    int dist;
    LeafResult(TreeNode n, int d) {
        node = n;
        dist = d;
    }
}
Powered by Vultr AgentBeta

Here's a concise description of how the solution operates:

Initialization: Two data structures, searchPath (a list) and memoization (a map), are initialized. searchPath captures the path from the root to the target node k, and memoization stores the results of subproblems to avoid redundant calculations.
Tree Exploration: The method exploreTree navigates through the binary tree recursively. It builds the path from the root to the node containing the integer k. If k is located, the reverse path building stops, and the method returns true, indicating k has been located.
Finding the Nearest Leaf: Once the path to k is identified, the method findClosestLeaf evaluates each node in this path for its proximity to the nearest leaf. It computes the distance from each node to its nearest leaf, which is minimized using the helper method getClosestLeaf.
Leaf Distance Calculation: The utility function getClosestLeaf calculates the nearest leaf for a given node using both its child nodes, considering previously computed results stored in memoization for optimization. This method recursively determines the least distance of the leaves from each subtree, adjusting the current node's leaf distance accordingly. If a node is a leaf (i.e., has no children), it directly returns itself with a distance of zero.
Output: The final result returned by the method findClosestLeaf is the value of the nearest leaf node.

More to Explore

Tech Talk: Running a Self-Improving AI Agent with Hermes on Vultr

Tech Talk: Implementing Fine-Grained Access Control with Vultr IAM

Tech Talk: Getting Started with Vultr IAM

Tech Talk: Simplifying Zero-Trust Networking with NetBird on Vultr Marketplace

0 Comments

Start the conversation

Be the first to comment and share your perspective with the community.