ബൈനറി ട്രീയിലെ ഒരു നോഡിന്റെ പൂർവ്വികൻ


വൈഷമ്യ നില ഹാർഡ്
പതിവായി ചോദിക്കുന്നു ആമസോൺ ഗൂഗിൾ
ബൈനറി ട്രീ വൃക്ഷം ട്രീ ട്രാവെർസൽ

പ്രശ്നം പ്രസ്താവന

“ബൈനറി ട്രീയിലെ ഒരു നോഡിന്റെ Kth പൂർവ്വികൻ” എന്ന പ്രശ്നം നിങ്ങൾക്ക് ഒരു നൽകിയിട്ടുണ്ടെന്ന് പറയുന്നു ബൈനറി ട്രീ ഒരു നോഡും. ഇപ്പോൾ ഈ നോഡിന്റെ kth പൂർവ്വികനെ കണ്ടെത്തേണ്ടതുണ്ട്. ഏതെങ്കിലും നോഡിന്റെ പൂർവ്വികൻ റൂട്ട് മുതൽ നോഡിന്റെ പാരന്റ് വരെയുള്ള പാതയിൽ കിടക്കുന്ന നോഡുകളാണ്.

ഉദാഹരണം

ബൈനറി ട്രീയിലെ ഒരു നോഡിന്റെ പൂർവ്വികൻ

2nd ancestor of 4 is 7

സമീപനം

തന്നിരിക്കുന്ന നോഡിന്റെ kth പൂർവ്വികനെ പ്രിന്റുചെയ്യാൻ പ്രശ്‌നം ആവശ്യപ്പെടുന്നു. ഒരു പൂർവ്വികൻ റൂട്ടിൽ നിന്ന് നോഡിന്റെ പാതയിൽ വരുന്ന നോഡുകളല്ലാതെ മറ്റൊന്നുമല്ല. ഒരു നോഡിന്റെ രക്ഷകർത്താവും അതിന്റെ പൂർവ്വികനാണ്.

ലളിതവും എളുപ്പവുമായ പരിഹാരം ഉപയോഗിക്കുക എന്നതാണ് BFS. ഈ പരിഹാരം എളുപ്പവും കാര്യക്ഷമവുമാണ്, പക്ഷേ ആദ്യം ഓരോ നോഡിന്റെയും രക്ഷകർത്താവ് ട്രീയിൽ സംഭരിക്കേണ്ടതുണ്ട്. ട്രീ കെ അകലത്തിൽ മുകളിലേക്ക് നീങ്ങുന്നതിന് പ്രശ്നം തിളച്ചുമറിയുന്നു. അതിനാൽ നോഡുകളുടെ കുട്ടികളെ തള്ളിവിടുന്നതിനുപകരം. ഓരോ നോഡിന്റെയും രക്ഷകർത്താവിനെ മാത്രമേ ഞങ്ങൾ പ്രേരിപ്പിക്കുകയുള്ളൂ.

എന്നാൽ ഈ പരിഹാരത്തിൽ, മുകളിൽ ചർച്ച ചെയ്ത സമീപനവുമായി പോകുന്നതിനുപകരം. ഞങ്ങൾ ഒരു ഉപയോഗിക്കും DFS അടിസ്ഥാനമാക്കിയുള്ള സമീപനം. DFS അടിസ്ഥാനമാക്കിയുള്ള സമീപനത്തിൽ, ഞങ്ങൾ ബാക്ക്‌ട്രാക്കിംഗ് പ്രയോജനപ്പെടുത്തുന്നു. ട്രീയിൽ‌ ഞങ്ങൾ‌ നോഡ് കണ്ടെത്തിക്കഴിഞ്ഞാൽ‌, ആവർത്തനത്തെ ഈ ആവർത്തന ഫംഗ്ഷൻ‌ എന്ന് വിളിക്കുന്ന ഫംഗ്ഷനിലേക്ക് തിരികെ നീങ്ങുന്നു. അതിനാൽ ഞങ്ങൾ k ചുവടുകൾ പിന്നോട്ട് നീക്കുമ്പോൾ, ലെവലിൽ നോഡ് പ്രിന്റുചെയ്യുന്നു. കാരണം അത് ഞങ്ങളുടെ kth പൂർവ്വികനും മടങ്ങിയെത്തുന്നതുമാണ്.

ഇതേ സമീപനമാണ് ബൈനറി ട്രീയുടെ inorder പിൻഗാമി.

കോഡ്

ബൈനറി ട്രീയിൽ ഒരു നോഡിന്റെ 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

സങ്കീർണ്ണത വിശകലനം

സമയ സങ്കീർണ്ണത

O (N), കാരണം ഏറ്റവും മോശമായ സാഹചര്യത്തിൽ ആവശ്യമായ നോഡ് കണ്ടെത്തുന്നതിന് മുമ്പായി എല്ലാ നോഡുകളിലൂടെയും സഞ്ചരിക്കേണ്ടി വരും.

ബഹിരാകാശ സങ്കീർണ്ണത

O (N), ആവർത്തന പ്രവർത്തനങ്ങൾക്കായി ഉപയോഗിക്കുന്ന കംപൈലർ സ്റ്റാക്ക് കാരണം.