Closest leaf node to a given node in Binary Tree in C++

By Saksham Agarwal

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:

Root to leaf path sum in a Binary tree in C++