Find the closest leaf in a Binary Tree - GeeksforGeeks


Find the closest leaf in a Binary Tree - GeeksforGeeks
Given a Binary Tree and a key 'k', find distance of the closest leaf from 'k'.
              A
            /    \    
           B       C
                 /   \  
                E     F   
               /       \
              G         H
             / \       /
            I   J     K

Closest leaf to 'H' is 'K', so distance is 1 for 'H'
Closest leaf to 'C' is 'B', so distance is 2 for 'C'
Closest leaf to 'E' is either 'I' or 'J', so distance is 2 for 'E' 
Closest leaf to 'B' is 'B' itself, so distance is 0 for 'B'
The main point to note here is that a closest key can either be a descendent of given key or can be reached through one of the ancestors.

The idea is to traverse the given tree in preorder and keep track of ancestors in an array. When we reach the given key, we evaluate distance of the closest leaf in subtree rooted with given key. We also traverse all ancestors one by one and find distance of the closest leaf in the subtree rooted with ancestor. We compare all distances and return minimum.



The above code can be optimized by storing the left/right information also in ancestor array. The idea is, if given key is in left subtree of an ancestors, then there is no point to call closestDown(). Also, the loop can that traverses ancestors array can be optimized to not traverse ancestors which are at more distance than current result.

Extend the above solution to print not only distance, but the key of closest leaf also
O(N^2)

    Node root;
      
    // A utility function to find minimum of x and y
    int getMin(int x, int y)
    {
        return (x < y) ? x : y;
    }
  
    // A utility function to find distance of closest leaf of the tree
    // rooted under given root
    int closestDown(Node node)
    {
        // Base cases
        if (node == null)
            return Integer.MAX_VALUE;
        if (node.left == null && node.right == null)
            return 0;
  
        // Return minimum of left and right, plus one
        return 1 + getMin(closestDown(node.left), closestDown(node.right));
    }
  
    // Returns distance of the cloest leaf to a given key 'k'.  The array
    // ancestors is used to keep track of ancestors of current node and
    // 'index' is used to keep track of curremt index in 'ancestors[]'
    int findClosestUtil(Node node, char k, Node ancestors[], int index)
    {
        // Base case
        if (node == null)
            return Integer.MAX_VALUE;
  
        // If key found
        if (node.data == k)
        {
            //  Find the cloest leaf under the subtree rooted with given key
            int res = closestDown(node);
  
            // Traverse all ancestors and update result if any parent node
            // gives smaller distance
            for (int i = index - 1; i >= 0; i--)
                res = getMin(res, index - i + closestDown(ancestors[i]));
            return res;
        }
  
        // If key node found, store current node and recur for left and
        // right childrens
        ancestors[index] = node;
        return getMin(findClosestUtil(node.left, k, ancestors, index + 1),
                findClosestUtil(node.right, k, ancestors, index + 1));
  
    }
  
    // The main function that returns distance of the closest key to 'k'. It
    // mainly uses recursive function findClosestUtil() to find the closes
    // distance.
    int findClosest(Node node, char k)
    {
        // Create an array to store ancestors
        // Assumptiom: Maximum height of tree is 100
        Node ancestors[] = new Node[100];
  
        return findClosestUtil(node, k, ancestors, 0);
    }
http://www.shuatiblog.com/blog/2015/10/07/closest-leaf-binary-tree/
int answer;

public int findClosest(TreeNode root, int key) {
    answer = Integer.MAX_VALUE;
    helper(root, key, new ArrayList<TreeNode>());
    return answer;
}

private void helper(TreeNode node, int key, List<TreeNode> path) {
    if (node == null) {
        return;
    } else if (node.val != key) {
        path.add(node);
        helper(node.left, key, path);
        helper(node.right, key, path);
        path.remove(path.size() - 1);
    } else {
        // key matches with current node value
        answer = lenToLowerLeaf(node);
        // answer initially = cloest leaf from lower

        int len = path.size();
        for (int i = 0; i < len; i++) {
            // for every ancestor, calculate distance and compare
            int ithToLowerLeaf = lenToLowerLeaf(path.get(i));
            answer = Math.min(answer, (len - i) + ithToLowerLeaf);
        }
    }
}

private int lenToLowerLeaf(TreeNode node) {
    if (node == null) {
        return Integer.MAX_VALUE;
    } else if (node.left == null && node.right == null) {
        return 0;
    } else {
        return 1 + Math.min(lenToLowerLeaf(node.left), lenToLowerLeaf(node.right));
    }
}
https://pradeepthangamuthu.wordpress.com/2015/03/02/find-the-closest-leaf-in-a-binary-tree/
O(N)
Here we need to find the closest leaf form the key.
Let's imagine you are going from bottom up in the tree.
So we start from a leaf and will go till the root.
So in each node going up we increment the value.
In each state choose the minimum value of left and right and increment.
So when we reach the key update the total_min with the minimum of left and right.
But we are not sure this is the minimum since the minimum can be from the parent of the current node also.
So now starts from the current node and mark  key_visited as true.
It returns the value of 1 because now we consider the distance form the current node in the upper path.
In going upper level check at each level, is this minimum by adding the left and right (Since we wanna go from the key to the current node and from the current node to the leaf) and compare it with the total_min.
In returning we wanna return the path from where the key lies ie left or right so to keep track of this we use left_visit.
If it is left visit we return left_min+1, or else it right visit and we return right_min+1.
So simply for going bottom to up we use post_order_traversal.

//This function performs post order traversal
int post_order_traversal(struct Node *current,char key,bool &key_visited,int &total_min)
{
    if(current==NULL)
        return 10000;

    if(current->left==NULL&&current->right==NULL)//To check if it's leaf
    {
        if(current->key==key)
            total_min=0;//incase the key is the leaf itself.
        return 1;
    }
    int left_min,right_min,current_min;

    bool left_visit=false;//To check where the key lies ie left or right while going back after visiting the key.
 
    left_min=post_order_traversal(current->left,key,key_visited,total_min);

    if(key_visited)//It will be true if the key lies on the left side since we not yet traversed right path.
        left_visit=true;
 
    right_min=post_order_traversal(current->right,key,key_visited,total_min);

    current_min=getMin(left_min,right_min);

    if(current->key==key)
    {
        total_min=getMin(total_min,current_min);
        key_visited=true;
        return 1;
    }
    if(key_visited)//Its used to find the distance from the top.
    {
        total_min=getMin(total_min,left_min+right_min); //left_min+right_min because we need to travel from key to current node and from current node to leaf.
        if(left_visit)
            return left_min+1;//if the key lies in the left side
        else
            return right_min+1;//if the key lies in the right side
    }
    return current_min+1;//1 is the distance from the current node to its parent. so its added to the minimum
}
int findClosest(struct Node *root,char key)
{
    int total_min=100000;//It contains the value of minimum closest leaf. Initially assigning some large value
    bool key_visited=false;//Used to check whether the key is visited
    post_order_traversal(root,key,key_visited,total_min);
    return total_min;
}
http://www.allenlipeng47.com/PersonalPage/index/view/91/nkey

Find all the ancestry of the target node, and the min-depth of them. Distance from target to its ancestry, plus distance from ancestry to ancestry's min-depth leaf is a potential result. Among them and the min-depth of the target node itself, find the smallest one.
The traversal process is:
For each node, it traverse the left and right sub-tree, and get the min-depth from each sub-tree. And it will return min-depth to its ancestry.
After traverse each sub-tree, if it found the target in either sub-tree, this node is treated as an ancestry of the target node. And the ancestry information should be stored.
In my code, I define a AncestryInfo class, to restore the ancestry information:
class AncestryInfo{
    int[] ancestry_record;    //records the ancestry nodes from target node. Target node is also included in position 0;
    int[] ancestry_level;    //records the min deep of ancestry nodes.
    int[] leaf;        //records the leaf which the ancestry nodes reach to the min deep
}
Extend the above solution to print not only distance, but the key of closest leaf also.
https://orajavasolutions.wordpress.com/2013/09/10/find-the-nearest-leaf-node-from-given-node-in-binary-tree/
A different question: the node's nearest leaf in its subtree - bfs, queue
    Node getNearestLeafNode(Node root)
    {
        if(root==null || (root.left ==null && root.right==null))
            return root;
         
        Queue<Node> queue = new LinkedList<Node>();
        queue.add(root);
        while(!queue.isEmpty()){
            Node n = queue.remove();
            if(n.left == null && n.right == null)
                return n;
            else
            {
                if(n.left!=null)
                    queue.add(n.left);
                if(n.right!=null)
                    queue.add(n.right);            
            }
        }
        return null;
    }
Read full article from Find the closest leaf in a Binary Tree - GeeksforGeeks

Labels

LeetCode (1432) GeeksforGeeks (1122) LeetCode - Review (1067) Review (882) Algorithm (668) to-do (609) Classic Algorithm (270) Google Interview (237) Classic Interview (222) Dynamic Programming (220) DP (186) Bit Algorithms (145) POJ (141) Math (137) Tree (132) LeetCode - Phone (129) EPI (122) Cracking Coding Interview (119) DFS (115) Difficult Algorithm (115) Lintcode (115) Different Solutions (110) Smart Algorithm (104) Binary Search (96) BFS (91) HackerRank (90) Binary Tree (86) Hard (79) Two Pointers (78) Stack (76) Company-Facebook (75) BST (72) Graph Algorithm (72) Time Complexity (69) Greedy Algorithm (68) Interval (63) Company - Google (62) Geometry Algorithm (61) Interview Corner (61) LeetCode - Extended (61) Union-Find (60) Trie (58) Advanced Data Structure (56) List (56) Priority Queue (53) Codility (52) ComProGuide (50) LeetCode Hard (50) Matrix (50) Bisection (48) Segment Tree (48) Sliding Window (48) USACO (46) Space Optimization (45) Company-Airbnb (41) Greedy (41) Mathematical Algorithm (41) Tree - Post-Order (41) ACM-ICPC (40) Algorithm Interview (40) Data Structure Design (40) Graph (40) Backtracking (39) Data Structure (39) Jobdu (39) Random (39) Codeforces (38) Knapsack (38) LeetCode - DP (38) Recursive Algorithm (38) String Algorithm (38) TopCoder (38) Sort (37) Introduction to Algorithms (36) Pre-Sort (36) Beauty of Programming (35) Must Known (34) Binary Search Tree (33) Follow Up (33) prismoskills (33) Palindrome (32) Permutation (31) Array (30) Google Code Jam (30) HDU (30) Array O(N) (29) Logic Thinking (29) Monotonic Stack (29) Puzzles (29) Code - Detail (27) Company-Zenefits (27) Microsoft 100 - July (27) Queue (27) Binary Indexed Trees (26) TreeMap (26) to-do-must (26) 1point3acres (25) GeeksQuiz (25) Merge Sort (25) Reverse Thinking (25) hihocoder (25) Company - LinkedIn (24) Hash (24) High Frequency (24) Summary (24) Divide and Conquer (23) Proof (23) Game Theory (22) Topological Sort (22) Lintcode - Review (21) Tree - Modification (21) Algorithm Game (20) CareerCup (20) Company - Twitter (20) DFS + Review (20) DP - Relation (20) Brain Teaser (19) DP - Tree (19) Left and Right Array (19) O(N) (19) Sweep Line (19) UVA (19) DP - Bit Masking (18) LeetCode - Thinking (18) KMP (17) LeetCode - TODO (17) Probabilities (17) Simulation (17) String Search (17) Codercareer (16) Company-Uber (16) Iterator (16) Number (16) O(1) Space (16) Shortest Path (16) itint5 (16) DFS+Cache (15) Dijkstra (15) Euclidean GCD (15) Heap (15) LeetCode - Hard (15) Majority (15) Number Theory (15) Rolling Hash (15) Tree Traversal (15) Brute Force (14) Bucket Sort (14) DP - Knapsack (14) DP - Probability (14) Difficult (14) Fast Power Algorithm (14) Pattern (14) Prefix Sum (14) TreeSet (14) Algorithm Videos (13) Amazon Interview (13) Basic Algorithm (13) Codechef (13) Combination (13) Computational Geometry (13) DP - Digit (13) LCA (13) LeetCode - DFS (13) Linked List (13) Long Increasing Sequence(LIS) (13) Math-Divisible (13) Reservoir Sampling (13) mitbbs (13) Algorithm - How To (12) Company - Microsoft (12) DP - Interval (12) DP - Multiple Relation (12) DP - Relation Optimization (12) LeetCode - Classic (12) Level Order Traversal (12) Prime (12) Pruning (12) Reconstruct Tree (12) Thinking (12) X Sum (12) AOJ (11) Bit Mask (11) Company-Snapchat (11) DP - Space Optimization (11) Dequeue (11) Graph DFS (11) MinMax (11) Miscs (11) Princeton (11) Quick Sort (11) Stack - Tree (11) 尺取法 (11) 挑战程序设计竞赛 (11) Coin Change (10) DFS+Backtracking (10) Facebook Hacker Cup (10) Fast Slow Pointers (10) HackerRank Easy (10) Interval Tree (10) Limited Range (10) Matrix - Traverse (10) Monotone Queue (10) SPOJ (10) Starting Point (10) States (10) Stock (10) Theory (10) Tutorialhorizon (10) Kadane - Extended (9) Mathblog (9) Max-Min Flow (9) Maze (9) Median (9) O(32N) (9) Quick Select (9) Stack Overflow (9) System Design (9) Tree - Conversion (9) Use XOR (9) Book Notes (8) Company-Amazon (8) DFS+BFS (8) DP - States (8) Expression (8) Longest Common Subsequence(LCS) (8) One Pass (8) Quadtrees (8) Traversal Once (8) Trie - Suffix (8) 穷竭搜索 (8) Algorithm Problem List (7) All Sub (7) Catalan Number (7) Cycle (7) DP - Cases (7) Facebook Interview (7) Fibonacci Numbers (7) Flood fill (7) Game Nim (7) Graph BFS (7) HackerRank Difficult (7) Hackerearth (7) Inversion (7) Kadane’s Algorithm (7) Manacher (7) Morris Traversal (7) Multiple Data Structures (7) Normalized Key (7) O(XN) (7) Radix Sort (7) Recursion (7) Sampling (7) Suffix Array (7) Tech-Queries (7) Tree - Serialization (7) Tree DP (7) Trie - Bit (7) 蓝桥杯 (7) Algorithm - Brain Teaser (6) BFS - Priority Queue (6) BFS - Unusual (6) Classic Data Structure Impl (6) DP - 2D (6) DP - Monotone Queue (6) DP - Unusual (6) DP-Space Optimization (6) Dutch Flag (6) How To (6) Interviewstreet (6) Knapsack - MultiplePack (6) Local MinMax (6) MST (6) Minimum Spanning Tree (6) Number - Reach (6) Parentheses (6) Pre-Sum (6) Probability (6) Programming Pearls (6) Rabin-Karp (6) Reverse (6) Scan from right (6) Schedule (6) Stream (6) Subset Sum (6) TSP (6) Xpost (6) n00tc0d3r (6) reddit (6) AI (5) Abbreviation (5) Anagram (5) Art Of Programming-July (5) Assumption (5) Bellman Ford (5) Big Data (5) Code - Solid (5) Code Kata (5) Codility-lessons (5) Coding (5) Company - WMware (5) Convex Hull (5) Crazyforcode (5) DFS - Multiple (5) DFS+DP (5) DP - Multi-Dimension (5) DP-Multiple Relation (5) Eulerian Cycle (5) Graph - Unusual (5) Graph Cycle (5) Hash Strategy (5) Immutability (5) Java (5) LogN (5) Manhattan Distance (5) Matrix Chain Multiplication (5) N Queens (5) Pre-Sort: Index (5) Quick Partition (5) Quora (5) Randomized Algorithms (5) Resources (5) Robot (5) SPFA(Shortest Path Faster Algorithm) (5) Shuffle (5) Sieve of Eratosthenes (5) Strongly Connected Components (5) Subarray Sum (5) Sudoku (5) Suffix Tree (5) Swap (5) Threaded (5) Tree - Creation (5) Warshall Floyd (5) Word Search (5) jiuzhang (5)

Popular Posts