Kth ancestor of a node in binary tree

Kth ancestor of a node in binary tree

Here given code implementation process.

/*
  C Program 
+ Kth ancestor of a node in binary tree
*/
#include <stdio.h>
#include <stdlib.h>
//structure of Binary Tree node
struct Node
{
  int data;
  struct Node*left,*right;
};
//Create a binary tree nodes and node fields (data,pointer) 
//And returning the reference of newly nodes

struct Node* insert(int data)
{
  //create dynamic memory to new binary tree node
  struct Node*new_node=(struct Node*)malloc(sizeof(struct Node));
  if(new_node!=NULL)
  {
    //set data and pointer values
    new_node->data=data;
    new_node->left=NULL; //Initially node left-pointer is NULL
    new_node->right=NULL;//Initially node right-pointer is NULL
  }
  else
  {
    printf("Memory Overflow\n");
    exit(0); //Terminate program execution
  }
  //return reference
  return new_node;
  
}
//Function which is finding  kth ancestor
void kth_LCA(struct Node*node,int data,int kth,int *status)
{

  if(node!=NULL && *status==0)
  {
    if(node->data==data)
    {
      *status=1;
    }
    else
    {
      //printf("%d\n",node->data );
      kth_LCA(node->left,data,kth,status);
      kth_LCA(node->right,data,kth,status); 
    }
    if(*status!=0)
    {

      if(*status==kth)
      {
        printf("Node [%d] %d-th Ancestor is %d\n",data,kth,node->data );
      }
      (*status)++;
      
    }

  }
}
//Function which are handle the request of find kth ancestor of a node
void find_lca(struct Node*node,int data,int kth)
{
  int status=0;
  if(node!=NULL)
  {
    kth_LCA(node, data, kth,&status);
    if(status==0)
    {
      printf("Node [%d] : Node Not found\n",data);
    }
    else if(status <= kth)
    {
      printf("Node [%d] %d-th Ancestor is : -1\n",data,kth);
    }
  }
  else
  {
    printf("Empty Binary Tree");
  }

}
int main()
{

  struct Node*root=NULL;
  int position=4;
  /*  Make A Binary Tree
  -----------------------
          1
         /  \
        2    3
       /    /  \
      4    5    6
       \       / \
        7     8   9
  */
  //Insertion of binary tree nodes
  root               =insert(1);
  root->left         =insert(2);
  root->right        =insert(3);
  root->right->right =insert(6);
  root->right->left  =insert(5);
  root->left->left   =insert(4);
  root->left->left->right =insert(7);
  root->right->right->left =insert(8);
  root->right->right->right =insert(9);


  find_lca(root,7,3); 
  find_lca(root,7,5);
  find_lca(root,9,4);
  find_lca(root,10,4);
  return 0;
}

Output

Node [7] 3-th Ancestor is 2
Node [7] 5-th Ancestor is : -1
Node [9] 4-th Ancestor is 1
Node [10] : Node Not found
/*
  C++ Program 
+ Kth ancestor of a node in binary tree
*/
#include <iostream>
using namespace std;

//Structure of Binary Tree node
class Node
{
public:
  int data;
  Node*left,*right;
  //make a tree node
  Node(int data)
  {
    //Assign field values
    this->data=data;
    left=right=NULL;
  }
};

class BinaryTree
{
public:
  Node*root;
  BinaryTree();
  void kth_LCA( Node*node,int data,int kth,int *status);
  void find_lca(int data,int kth);
};

//set initial tree root to NULL
BinaryTree:: BinaryTree()
{
  root=NULL;
}

//Function which is finding  kth ancestor
void BinaryTree:: kth_LCA( Node*node,int data,int kth,int *status)
{
    if (node!=NULL && *status==0)
    {
      if (node->data==data)
      {
        *status=1;
      }
      else
      {
   
        kth_LCA(node->left,data,kth,status);
        kth_LCA(node->right,data,kth,status); 
      }
      if (*status!=0)
      {
        if (*status==kth)
        {
          cout<<"Node ["<<data<<"] "<<kth <<"-th Ancestor is "<<node->data  <<"\n";
        }
        (*status)++;
        
      }
    }
}
//Function which are handle the request of find kth ancestor of a node
void BinaryTree:: find_lca(int data,int kth)
{
    int status=0;
    if (root!=NULL)
    {
      kth_LCA(root, data, kth,&status);
      if (status==0)
      {
        cout<<"Node ["<< data <<"] : Node Not found\n";
      }
      else if (status <= kth)
      {
        cout<<"Node ["<<data <<"] "<<kth <<"-th Ancestor is : -1\n";
      }
    }
    else
    {
      cout<<"Empty Binary Tree";
    }
}
int main()
{

  BinaryTree obj;
  /*  Make A Binary Tree
  -----------------------
      1
     /  \
    2    3
   /    /  \
  4    5    6
   \       / \
    7     8   9
  */
  //Insertion of binary tree nodes
  obj.root               =new Node(1);
  obj.root->left         =new Node(2);
  obj.root->right        =new Node(3);
  obj.root->right->right =new Node(6);
  obj.root->right->left  =new Node(5);
  obj.root->left->left   =new Node(4);
  obj.root->left->left->right =new Node(7);
  obj.root->right->right->left =new Node(8);
  obj.root->right->right->right =new Node(9);
  //7 is node and 3 is kth ancestor
  obj.find_lca(7,3); 
  obj.find_lca(7,5);
  obj.find_lca(9,4);
  obj.find_lca(10,4);
  return 0;
}

Output

Node [7] 3-th Ancestor is 2
Node [7] 5-th Ancestor is : -1
Node [9] 4-th Ancestor is 1
Node [10] : Node Not found
/*
Java Program 
Kth ancestor of a node in binary tree
*/

//Class of Binary Tree node
class Node
{

  public int data;
  public Node left, right;
  //make a tree node
  public Node(int data)
  {
    //assign field values
    this.data=data;
    left=right=null;
  }
};

public class BinaryTree
{

  public Node root;
  private int status;

  public BinaryTree()
  {
    //set initial tree root to null
    root=null;
    status=0;

  }
  //Function which is finding  kth ancestor
  public void kth_LCA( Node node,int data,int kth)
  {
      if (node!=null &&  status==0)
      {
        if (node.data==data)
        {
           status=1;
        }
        else
        {
     
          kth_LCA(node.left,data,kth);
          kth_LCA(node.right,data,kth); 
        }
        if (status!=0)
        {
          if (status==kth)
          {
            System.out.print ("Node ["+data+"] "+kth +"-th Ancestor is "+node.data  +"\n");
          }
          status++;
          
        }
      }
  }
  //Function which are handle the request of find kth ancestor of a node
  public void  find_lca(int data,int kth)
  {
      status=0;
      if (root!=null)
      {
        kth_LCA(root, data, kth);
        if (status==0)
        {
          System.out.print ("Node ["+ data +"] : Node Not found\n");
        }
        else if (status <= kth)
        {
          System.out.print ("Node ["+data +"] "+kth +"-th Ancestor is : -1\n");
        }
      }
      else
      {
        System.out.print("Empty Binary Tree\n");
      }
  }

  public static void main(String[] args)
  {
    //Make object of Binary Tree
    BinaryTree obj=new BinaryTree();

    /*  Make A Binary Tree
    -----------------------
        1
       /  \
      2    3
     /    /  \
    4    5    6
     \       / \
      7     8   9
    */
    //Insertion of binary tree nodes
    obj.root               = new Node(1);
    obj.root.left         = new Node(2);
    obj.root.right        = new Node(3);
    obj.root.right.right   = new Node(6);
    obj.root.right.left     = new Node(5);
    obj.root.left.left      = new Node(4);
    obj.root.left.left.right = new Node(7);
    obj.root.right.right.left = new Node(8);
    obj.root.right.right.right = new Node(9);
    //7 is node and 3 is kth ancestor
    obj.find_lca(7,3); 
    obj.find_lca(7,5);
    obj.find_lca(9,4);
    obj.find_lca(10,4);


  }
}

Output

Node [7] 3-th Ancestor is 2
Node [7] 5-th Ancestor is : -1
Node [9] 4-th Ancestor is 1
Node [10] : Node Not found
#Python Program 
#Kth ancestor of a node in binary tree
 
class Node:
  def __init__(self,data):
    #Assign node value
    self.data=data
    self.left,self.right=None,None


class BinaryTree:

  def __init__(self):
    #set initial tree root to None
    self.root=None
    self.status=0

  #Function which is finding  kth ancestor
  def kth_LCA(self,node, data, kth) :

    if (node!=None  and  self.status==0) :

      if (node.data==data) :

        self.status=1
      else :

        self.kth_LCA(node.left,data,kth)
        self.kth_LCA(node.right,data,kth) 
      if (self.status!=0) :

        if (self.status==kth) :

          print("Node [",data,"] ",kth ,"-th Ancestor is ",node.data  ,"\n")

        self.status += 1

  #Function which are handle the request of find kth ancestor of a node
  def find_lca(self, data, kth) :

    self.status=0
    if (self.root!=None) :

      self.kth_LCA(self.root,data,kth)
      if (self.status==0) :

        print("Node [", data ,"] : Node Not found\n")

      elif (self.status <= kth) :

        print("Node [",data ,"] ",kth ,"-th Ancestor is : -1\n")

    else :

      print("Empty Binary Tree")

    
def main():

 #Make object of Binary Tree
  obj= BinaryTree()
  #  Make A Binary Tree
  # 
  #      1
  #     /  \
  #    2    3
  #   /    /  \
  #  4    5    6
  #   \       / \
  #    7     8   9
  #  
  #Insertion of binary tree nodes
  obj.root               = Node(1)
  obj.root.left         = Node(2)
  obj.root.right        = Node(3)
  obj.root.right.right = Node(6)
  obj.root.right.left  = Node(5)
  obj.root.left.left   = Node(4)
  obj.root.left.left.right = Node(7)
  obj.root.right.right.left = Node(8)
  obj.root.right.right.right = Node(9)
  #7 is node and 3 is kth ancestor
  obj.find_lca(7,3) 
  obj.find_lca(7,5)
  obj.find_lca(9,4)
  obj.find_lca(10,4)

if __name__=="__main__":
  main()

Output

Node [ 7 ]  3 -th Ancestor is  2 

Node [ 7 ]  5 -th Ancestor is : -1

Node [ 9 ]  4 -th Ancestor is  1 

Node [ 10 ] : Node Not found

/*
C# Program 
Kth ancestor of a node in binary tree
*/
using System;
//Class of Binary Tree node
public class Node
{

  public int data;
  public Node left, right;
  //make a tree node
  public Node(int data)
  {
    //assign field values
    this.data=data;
    left=right=null;
  }
};

public class BinaryTree
{

  public Node root;
  private int status;

  public BinaryTree()
  {
    //set initial tree root to null
    root=null;
    status=0;

  }
  //Function which is finding  kth ancestor
  public void kth_LCA( Node node,int data,int kth)
  {
    if (node!=null &&  status==0)
    {
      if (node.data==data)
      {
        status=1;
      }
      else
      {

        kth_LCA(node.left,data,kth);
        kth_LCA(node.right,data,kth); 
      }
      if (status!=0)
      {
        if (status==kth)
        {
          Console.Write ("Node ["+data+"] "+kth +"-th Ancestor is "+node.data  +"\n");
        }
        status++;

      }
    }
  }
  //Function which are handle the request of find kth ancestor of a node
  public void  find_lca(int data,int kth)
  {
    status=0;
    if (root!=null)
    {
      kth_LCA(root, data, kth);
      if (status==0)
      {
        Console.Write ("Node ["+ data +"] : Node Not found\n");
      }
      else if (status <= kth)
      {
        Console.Write ("Node ["+data +"] "+kth +"-th Ancestor is : -1\n");
      }
    }
    else
    {
      Console.Write("Empty Binary Tree\n");
    }
  }

  public static void Main(String[] args)
  {
    //Make object of Binary Tree
    BinaryTree obj=new BinaryTree();

    /*  Make A Binary Tree
    -----------------------
        1
       /  \
      2    3
     /    /  \
    4    5    6
     \       / \
      7     8   9
    */
    //Insertion of binary tree nodes
    obj.root               = new Node(1);
    obj.root.left         = new Node(2);
    obj.root.right        = new Node(3);
    obj.root.right.right   = new Node(6);
    obj.root.right.left     = new Node(5);
    obj.root.left.left      = new Node(4);
    obj.root.left.left.right = new Node(7);
    obj.root.right.right.left = new Node(8);
    obj.root.right.right.right = new Node(9);
    //7 is node and 3 is kth ancestor
    obj.find_lca(7,3); 
    obj.find_lca(7,5);
    obj.find_lca(9,4);
    obj.find_lca(10,4);


  }
}

Output

Node [7] 3-th Ancestor is 2
Node [7] 5-th Ancestor is : -1
Node [9] 4-th Ancestor is 1
Node [10] : Node Not found
<?php
//Php program 
//Kth ancestor of a node in binary tree
class Node
{
  public $data;
  public $left;
  public $right;

  function __construct($data)
  {
    $this->data = $data;
    $this->left = NULL;
    $this->right = NULL;
  }
}
class BinaryTree
{

  public $root;
  function __construct()
  {
    //set initial tree root to null
    $this->root=NULL;
  }
  //Function which is finding  kth ancestor
  public function  kth_LCA($node, $data, $kth, &$status)
  {
    if ($node!=NULL && $status==0)
    {
      if ($node->data==$data)
      {
        $status=1;
      }
      else
      {
   
        $this->kth_LCA($node->left,$data,$kth,$status);
        $this->kth_LCA($node->right,$data,$kth,$status); 
      }
      if ($status!=0)
      {
        if ($status==$kth)
        {
          echo "Node [".$data."] ".$kth ."-th Ancestor is ".$node->data  ."\n";
        }
        $status++;
        
      }
    }
  }
  //Function which are handle the request of find kth ancestor of a node
  public function find_lca( $data, $kth)
  {
    $status=0;
    if ($this->root!=NULL)
    {
      $this->kth_LCA($this->root,$data,$kth,$status);
      if ($status==0)
      {
        echo "Node [". $data ."] : Node Not found\n";
      }
      else if ($status <= $kth)
      {
        echo "Node [".$data ."] ".$kth ."-th Ancestor is : -1\n";
      }
    }
    else
    {
      echo "Empty Binary Tree";
    }
  }


}
function main()
{
  //Make object of Binary Tree
  $obj=new BinaryTree();

  /*  Make A Binary Tree
  -----------------------
      1
     /  \
    2    3
   /    /  \
  4    5    6
   \       / \
    7     8   9
  */
  //Insertion of binary tree nodes
  $obj->root               =new Node(1);
  $obj->root->left         =new Node(2);
  $obj->root->right        =new Node(3);
  $obj->root->right->right =new Node(6);
  $obj->root->right->left  =new Node(5);
  $obj->root->left->left   =new Node(4);
  $obj->root->left->left->right =new Node(7);
  $obj->root->right->right->left =new Node(8);
  $obj->root->right->right->right =new Node(9);
  //7 is node and 3 is kth ancestor
  $obj->find_lca(7,3); 
  $obj->find_lca(7,5);
  $obj->find_lca(9,4);
  $obj->find_lca(10,4);
}
main();
?>

Output

Node [7] 3-th Ancestor is 2
Node [7] 5-th Ancestor is : -1
Node [9] 4-th Ancestor is 1
Node [10] : Node Not found


Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.

New Comment







© 2021, kalkicode.com, All rights reserved