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'.
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.
http://www.shuatiblog.com/blog/2015/10/07/closest-leaf-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&¤t->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.
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
Read full article from 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); }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));
}
}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&¤t->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.
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.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
}
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; }