बाइनरी ट्री में एक नोड का केथ पूर्वज


कठिनाई स्तर कठिन
में अक्सर पूछा वीरांगना गूगल
बाइनरी ट्री पेड़ वृक्ष का त्राटक

समस्या का विवरण

समस्या "बाइनरी ट्री में एक नोड के केएच पूर्वज" कहती है कि आपको ए बाइनरी ट्री और एक नोड। अब हमें इस नोड के kth पूर्वज को खोजने की आवश्यकता है। किसी भी नोड का पूर्वज नोड्स है जो रूट से नोड के माता-पिता के लिए झूठ बोलता है।

उदाहरण

बाइनरी ट्री में एक नोड का केथ पूर्वज

2nd ancestor of 4 is 7

दृष्टिकोण

समस्या किसी दिए गए नोड के kth पूर्वज को प्रिंट करने के लिए कहती है। पूर्वज कुछ भी नहीं है, लेकिन नोड्स जो रूट से नोड के रास्ते में आते हैं। एक नोड का मूल भी इसका पूर्वज है।

एक सरल और आसान समाधान का उपयोग करना है वित्तीय पर्यवेक्षण बोर्ड। यह समाधान आसान और कुशल भी है, लेकिन हमें पहले पेड़ में प्रत्येक नोड के माता-पिता को संग्रहीत करने की आवश्यकता है। तब समस्या बस के k दूरी पर बढ़ने के लिए उबलती है। इसलिए बच्चों को धक्का देने की बजाये। हम केवल प्रत्येक नोड के माता-पिता को धक्का देंगे।

लेकिन इस समाधान में, ऊपर चर्चा किए गए दृष्टिकोण के साथ जाने के बजाय। हम एक का उपयोग करेंगे डीएफएस आधारित दृष्टिकोण। डीएफएस आधारित दृष्टिकोण में, हम बैकट्रैकिंग का लाभ उठा रहे हैं। एक बार जब हम पेड़ में नोड पाते हैं, तो पुनरावृत्ति उस फ़ंक्शन पर वापस जाती रहती है जिसे इस पुनरावर्ती फ़ंक्शन कहा जाता है। इसलिए जब हम 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

जटिलता विश्लेषण

समय जटिलता

पर), क्योंकि सबसे खराब स्थिति में सभी नोड्स को पीछे करना पड़ सकता है जिससे पहले हमें आवश्यक नोड मिल जाए।

अंतरिक्ष जटिलता

पर), क्योंकि संकलक कार्यों के लिए इस्तेमाल किया जा रहा है जो कंपाइलर स्टैक के कारण।