Closest leaf node to a given node in Binary Tree in C++
In this tutorial, we’ll see how to find the closest leaf to a node in a Binary tree in C++.
Some Terminology:
Leaf node:
A leaf node in a binary tree is a node that has no child nodes.
Binary Tree:
A binary tree is a tree data structure with only 2 child nodes.
Intuition:
To find the closest leaf to any node in a tree, there are only 2 possibilities :
- Either the closest leaf is in the subtree from this node
- Or the closest leaf path goes through one of the ancestors of the node
So the sequence would go as follows:
- We first check what is the closest distance to a leaf in the subtree of the node.
- Then we go through all the parents in a loop till we reach the root and see the closest leaf to the subtree in the left part if the node is in the right subpart, or else the vice-a-versa.
- Then we compare these 2 distances obtained from the desired node’s subtree and the parent node and take the smallest one
Note: Here when we will compare the desired node subtree path to the parent node left/right subtree path there will be an additional factor of the length from parent to non-desired node subtree and the length of parent to the desired node subtree.
Find closest leaf node to a given node in Binary Tree in C++
#include <stdio.h> #include <bits/stdc++.h> using namespace std; /* My Node Data structure is a little special As it stores whether the parent node of a node Also it stores if it is present in the right or the left child of the parent node */ typedef struct Node{ struct Node* left; struct Node* right; struct Node* parent; int value; //Child Type = 'L' for left child | Child Type = 'R' for right child char ChildType; }Node; //A function to create a NULL node Node* CreateNode(int value) { Node* temp = new Node(); temp->value = value; temp->left = temp->right = temp->parent = NULL; return temp; } //A function to set the left child void SetLeftChild(Node* root,int value) { root->left = new Node(); root->left->value = value; root->left->ChildType = 'L'; root->left->parent = root; } //A function to set the right child void SetRightChild(Node* root,int value) { root->right = new Node(); root->right->value = value; root->right->ChildType = 'R'; root->right->parent = root; } //This function checks the Closest Leaf in the subtree of the node x and returns the value //into ClosestDist void ClosestLeafSubtree(Node* x,int lvl,int* ClosestDist) { if(x == NULL) return; //------If we get to a leaf node we check if the distance till this node---- //--------------------is the minimum till now or not------------------------- if(x->left == NULL && x->right == NULL) { if(lvl < *ClosestDist) *ClosestDist = lvl; return; } //--------Recursively going through the left and right subtree------- //-------------and increasing the level/path dist by 1---------------- ClosestLeafSubtree(x->left,lvl + 1,ClosestDist); ClosestLeafSubtree(x->right,lvl + 1,ClosestDist); } void ClosestLeafDist(Node* x,int* closestDist) { //Setting a initial closest distance to be that from the subtree of the node ClosestLeafSubtree(x,0,closestDist); //cout<<*closestDist; //This is distance from parent.[Initially,from the first parent = 1] int dist_from_parent = 1; //--------Creating a temp Node so as to not change the input node------- Node* s = x; //Looping through all the parents of the input node util we reach root while(s->parent != NULL) { //If our input node is in the right subtree of the parent node if(s->ChildType == 'R') { //Find the Closest Leaf in the left subtree of parent int* temp_dist = new int(INT_MAX); ClosestLeafSubtree(s->parent->left,0,temp_dist); //----------------Check how our previous values compares to----------------- // closestLeaf + (dist of leftsubtree to root = 1) + dist to desired node if(*temp_dist+dist_from_parent+1<*closestDist) *closestDist = *temp_dist+dist_from_parent+1; } //Else our input node is in the left subtree of the parent node else { //Find the Closest Leaf in the right subtree of parent int* temp_dist = new int(INT_MAX); ClosestLeafSubtree(s->parent->right,0,temp_dist); if(*temp_dist + dist_from_parent + 1<*closestDist) *closestDist = *temp_dist + dist_from_parent + 1; } //We increase the distance from parent as we move to the previous ancestor dist_from_parent += 1; //We move to the previous ancestor s = s->parent; } } int main(void) { Node* root = CreateNode(1); SetLeftChild(root,12); SetRightChild(root,13); SetLeftChild(root->right,13); SetLeftChild(root->right->left,13); SetLeftChild(root->right->left->left,13); SetRightChild(root->right,13); SetRightChild(root->right->right,13); SetRightChild(root->right->right->right,13); SetRightChild(root->right->right->right->right,13); SetRightChild(root->right->right->right->right->right,13); int* closestDist = new int(INT_MAX); ClosestLeafDist(root->right->right,closestDist); cout<<*closestDist; return 0; }
Output: 3
Also read:
Leave a Reply