బైనరీ చెట్టులోని నోడ్ యొక్క Kth పూర్వీకుడు


కఠినత స్థాయి హార్డ్
తరచుగా అడుగుతుంది అమెజాన్ గూగుల్
బైనరీ చెట్టు ట్రీ చెట్టు ట్రావెర్సల్

సమస్యల నివేదిక

“బైనరీ చెట్టులోని నోడ్ యొక్క Kth పూర్వీకుడు” సమస్య మీకు ఇవ్వబడింది బైనరీ చెట్టు మరియు నోడ్. ఇప్పుడు మనం ఈ నోడ్ యొక్క kth పూర్వీకుడిని కనుగొనాలి. ఏదైనా నోడ్ యొక్క పూర్వీకుడు నోడ్ యొక్క మూలం నుండి పేరెంట్ వరకు ఉన్న నోడ్లు.

ఉదాహరణ

బైనరీ చెట్టులోని నోడ్ యొక్క Kth పూర్వీకుడు

2nd ancestor of 4 is 7

అప్రోచ్

ఇచ్చిన నోడ్ యొక్క kth పూర్వీకుడిని ముద్రించడానికి సమస్య అడుగుతుంది. పూర్వీకుడు రూట్ నుండి నోడ్ యొక్క మార్గంలో వచ్చే నోడ్స్ తప్ప మరొకటి కాదు. నోడ్ యొక్క పేరెంట్ కూడా దాని పూర్వీకుడు.

సరళమైన మరియు సులభమైన పరిష్కారం ఉపయోగించడం BFS. ఈ పరిష్కారం సులభం మరియు సమర్థవంతమైనది కాని మొదట ప్రతి నోడ్ యొక్క పేరెంట్‌ను చెట్టులో భద్రపరచడం అవసరం. అప్పుడు సమస్య చెట్టు k దూరం పైకి కదలడానికి దిమ్మదిరుగుతుంది. కాబట్టి నోడ్స్ పిల్లలను నెట్టే బదులు. మేము ప్రతి నోడ్ యొక్క పేరెంట్‌ను మాత్రమే నెట్టివేస్తాము.

కానీ ఈ పరిష్కారంలో, పైన చర్చించిన విధానంతో వెళ్ళే బదులు. మేము ఉపయోగిస్తాము a DFS ఆధారిత విధానం. DFS ఆధారిత విధానంలో, మేము బ్యాక్‌ట్రాకింగ్ ప్రయోజనాన్ని పొందుతున్నాము. మేము చెట్టులోని నోడ్‌ను కనుగొన్న తర్వాత, పునరావృతం ఈ పునరావృత ఫంక్షన్ అని పిలువబడే ఫంక్షన్‌కు తిరిగి వెళుతుంది. కాబట్టి మేము k దశలను వెనక్కి తరలించినప్పుడు, మేము నోడ్‌ను స్థాయిలో ప్రింట్ చేస్తాము. ఎందుకంటే అది మన kth పూర్వీకుడు మరియు తిరిగి శూన్యమైనది.

అదే విధానాన్ని ఉపయోగిస్తారు బైనరీ చెట్టు యొక్క క్రమరహిత వారసుడు.

కోడ్

బైనరీ చెట్టులో నోడ్ యొక్క Kth పూర్వీకుడిని కనుగొనడానికి C ++ కోడ్

#include<bits/stdc++.h>
using namespace std;

struct node {
  int data;
  node *left, *right;
};

node* create(int data){
  node* tmp = new node();
  tmp->data = data;
  tmp->left = tmp->right = NULL;
  return tmp;
}

node* tmp = NULL;

node* kthAncestor(node *root, int cur, int &k)
{
  if (root == NULL)
    return NULL;
  if (root->data == cur || (tmp = kthAncestor(root->left,cur,k)) || (tmp = kthAncestor(root->right,cur,k))){
    if(k)k--;
    else if (k == 0){
      cout<<"kth ancestor of "<<cur<<" is "<<root->data;
      return NULL;
    }
    return root;
  }
}

int main()
{
  node* root = create(5);
  root->left = create(7);
  root->right = create(3);
  root->left->left = create(9);
  root->left->right = create(6);
  root->left->right->left = create(1);
  root->left->right->right = create(4);
  int k = 2;
  kthAncestor(root, 4, k);
}
kth ancestor of 4 is 7

బైనరీ చెట్టులోని నోడ్ యొక్క Kth పూర్వీకుడిని కనుగొనడానికి జావా కోడ్

import java.util.*;
class node{
  int data;
  node left, right;
}
class Main{

  static node create(int data){
    node tmp = new node();
    tmp.data = data;
    tmp.left = tmp.right = null;
    return tmp;
  }

  	static int k = 2;
  static node tmp = null;

  static node kthAncestor(node root, int cur)
  {
    if (root == null)
      return null;
    if ((root.data == cur) || ((tmp = kthAncestor(root.left,cur)) != null) || ((tmp = kthAncestor(root.right,cur)) != null)){
      if(k > 0)k--;
      else if (k == 0){
        System.out.print("kth ancestor of "+cur+" is "+root.data);
        return null;
      }
      return root;
    }
    return null;
  }

  public static void main(String[] args)
  {
    node root = create(5);
    root.left = create(7);
    root.right = create(3);
    root.left.left = create(9);
    root.left.right = create(6);
    root.left.right.left = create(1);
    root.left.right.right = create(4);
    k = 2;
    kthAncestor(root, 4);
  }
}
kth ancestor of 4 is 7

సంక్లిష్టత విశ్లేషణ

సమయం సంక్లిష్టత

పై), ఎందుకంటే చెత్త సందర్భంలో మేము అవసరమైన నోడ్‌ను కనుగొనే ముందు అన్ని నోడ్‌లను దాటవలసి ఉంటుంది.

అంతరిక్ష సంక్లిష్టత

పై), కంపైలర్ స్టాక్ కారణంగా ఇది పునరావృత ఫంక్షన్లకు ఉపయోగించబడుతోంది.