બાઈનરી ટ્રીની બાઉન્ડ્રી ટ્રાવર્સલ


મુશ્કેલી સ્તર મધ્યમ
વારંવાર પૂછવામાં આવે છે ભેગા એમેઝોન પર્યટન કૃતિકાલ ઉકેલો માઈક્રોસોફ્ટ મોર્ગન સ્ટેન્લી પે સ્નેપડીલ
દ્વિસંગી વૃક્ષ વૃક્ષ વૃક્ષ આડેધડ

સમસ્યા નિવેદન

"બાઈનરી ટ્રીની બાઉન્ડ્રી ટ્રાવર્સલ" સમસ્યા જણાવે છે કે તમને બાઈનરી ટ્રી આપવામાં આવે છે. હવે તમારે a નું બાઉન્ડ્રી વ્યૂ છાપવાની જરૂર છે દ્વિસંગી વૃક્ષ. અહીં બાઉન્ડ્રી ટ્રાવર્સલ એટલે કે બધા ગાંઠો ઝાડની સીમા તરીકે બતાવવામાં આવે છે. ગાંઠો ઉપરની બાજુથી, ડાબી બાજુથી, નીચેની બાજુથી અને જમણી બાજુથી, ઘડિયાળની વિરુદ્ધ દિશામાં દેખાય છે. પરંતુ જો આપણે આ બધા દૃશ્યો સીધા જ છાપ્યા હોત, તો તેના પરિણામ રૂપે તે જ ગાંઠો ઘણી વખત છાપવામાં આવશે. તેથી બાઉન્ડ્રી વ્યુ છાપો જેમ કે ગાંઠો પુનરાવર્તિત ન થાય.

ઉદાહરણ

2 3 5 6 4 7

સમજૂતી

અહીં, બધા ગાંઠો બાઉન્ડ્રી નોડ્સ છે. પરંતુ આપણે ગાંઠો વિરોધી દિશામાં છાપવાની જરૂર છે. આમ આપણે 2 ની મૂળથી શરૂ કરીએ છીએ. પછી, આપણે ફક્ત તે જ રીતે આગળ વધીએ છીએ અને ગાંઠો 2, 3, 4, 6, 4, 7 છાપીશું.

બાઈનરી ટ્રીની બાઉન્ડ્રી ટ્રાવર્સલ

5 7 9 1 4 3

અભિગમ

સમસ્યા અમને ઝાડની બાઉન્ડ્રી છાપવા માટે કહે છે, અહીં આપણે ડાબી, જમણી અને નીચેની સીમા રાખી છે. જો ઝાડની કોઈ ડાબી અથવા જમણી સીમા નથી. રુટ પોતે ડાબી અથવા જમણી સીમા તરીકે માનવામાં આવે છે. આમાં એક શરત પણ છે કે જો આપણે બાઉન્ડ્રી નોડ્સ છાપીએ, તો આપણે કાળજી લેવાની જરૂર છે કે બે ગાંઠોમાંથી કોઈ પણ ઘણી વખત છાપવામાં ન આવે.

સમસ્યા હલ કરવા માટે, અમે ઝાડની ડાબી સીમાથી પ્રારંભ કરીશું. આપણે કહી શકીએ કે જો નોડ ડાબી બાજુથી દેખાય તો તે નોડ ડાબી સીમાની છે. એ જ રીતે, અમે જમણી બાજુના ગાંઠો અને પાંદડા ગાંઠો વ્યાખ્યાયિત કરીએ છીએ. ડાબી સીમા છાપવા માટે, અમે ઝાડને એવી રીતે પસાર કરીશું કે જો મૂળમાં ડાબી બાજુ નોડ હોય તો, પછી તેના જમણા નોડ પર ખસેડો. એકવાર આપણે પર્ણ નોડ પર પહોંચીશું. અમે પર્ણ ગાંઠોને છાપતા નથી કારણ કે આપણે વારંવાર પર્ણ ગાંઠો અલગથી છાપીએ છીએ. એકવાર આપણે ડાબી બાઉન્ડ્રી સાથે થઈ ગયાં.

આપણે લીફ ગાંઠો છાપીએ છીએ, પ્રથમ વારંવાર ડાબી સબટ્રી પાંદડા છાપવા દ્વારા. ડાબી સબટ્રી પાંદડા છાપ્યા પછી જમણા સબટ્રીમાં પાંદડા છાપો. આ રીતે બધા પાંદડા ગાંઠો વિરોધી ઘડિયાળની દિશામાં છાપવામાં આવશે. એકવાર અમે પાંદડા છાપીશું, પછી આપણે જમણી સીમાના ગાંઠો છાપીશું. આ સમયે ગાંઠોને નીચે-નીચેની રીતે છાપવાની જરૂર છે. આમ અંદર રિકર્ઝન, પહેલા આપણે ઝાડની ડાબી અથવા જમણી સબટ્રી હલ કરીએ અને પછી વર્તમાન નોડને પીક્રોપ્રિન્ટ કરીએ.

બાઈનરી ટ્રીની બાઉન્ડ્રી ટ્રાવેર્સલ છાપવા માટે સી ++ કોડ

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

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

// print the leaves (nodes from the bottom)
void printLeaves(node* root)
{
  if(root){
    // recursively solve the problem for the left subtree
    printLeaves(root->left);
    // if current node is a leaf
    if ((root->left) == NULL && (root->right) == NULL)
      cout<<root->data<<" ";
    // recursively solve the problem for right subtree
    printLeaves(root->right);
  }
}

// print all the nodes of left boundary
// this function will not print the leaves viewed from left side
void printLeft(node* root)
{
  if(root){
    if(root->left != NULL){
      cout<<root->data<<" ";
      // recursively move down the left subtree
      printLeft(root->left);
    }
    else if(root->right){
      cout<<root->data<<" ";
      // recursively move down the right subtree
      printLeft(root->right);
    }
  }
}

// print all the nodes of right boundary
// this function will not print the leaves viewed from the right side
void printRight(node* root)
{
  // printing is done after moving down the tree
  // thus printing is done in bottom up manner
  if(root){
    if (root->right) {
      printRight(root->right);
      cout<<root->data<<" ";
    }
    else if (root->left) {
      printRight(root->left);
      cout<<root->data<<" ";
    }
  }
}

void boundaryUtil(node* root)
{
  // first print the root, then print the left boundary
  // then the leaves which are seen from bottom
  // at last print the right boundary
  if(root){
    cout<<root->data<<" ";
    printLeft(root->left);
    printLeaves(root->left);
    printLeaves(root->right);
    printRight(root->right);
  }
}

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

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);

  boundaryUtil(root);
}
5 7 9 1 4 3

બાઈનરી ટ્રીની બાઉન્ડ્રી ટ્રાવેર્સલ છાપવા માટે જાવા કોડ

import java.util.*;

class node{
  int data;
  node left, right;
}

class Main{

  // print the leaves (nodes from the bottom)
  static void printLeaves(node root)
  {
    if(root != null){
      // recursively solve the problem for the left subtree
      printLeaves(root.left);
      // if current node is a leaf
      if ((root.left) == null && (root.right) == null)
        System.out.print(root.data+" ");
      // recursively solve the problem for right subtree
      printLeaves(root.right);
    }
  }

  // print all the nodes of left boundary
  // this function will not print the leaves viewed from left side
  static void printLeft(node root)
  {
    if(root != null){
      if(root.left != null){
        System.out.print(root.data+" ");
        // recursively move down the left subtree
        printLeft(root.left);
      }
      else if(root.right != null){
        System.out.print(root.data+" ");
        // recursively move down the right subtree
        printLeft(root.right);
      }
    }
  }

  // print all the nodes of right boundary
  // this function will not print the leaves viewed from the right side
  static void printRight(node root)
  {
    // printing is done after moving down the tree
    // thus printing is done in bottom up manner
    if(root != null){
      if(root.right != null){
        printRight(root.right);
        System.out.print(root.data+" ");
      }
      else if(root.left != null){
        printRight(root.left);
        System.out.print(root.data+" ");
      }
    }
  }

  static void boundaryUtil(node root)
  {
    // first print the root, then print the left boundary
    // then the leaves which are seen from bottom
    // at last print the right boundary
    if(root != null){
      System.out.print(root.data+" ");
      printLeft(root.left);
      printLeaves(root.left);
      printLeaves(root.right);
      printRight(root.right);
    }
  }

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

  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);

    boundaryUtil(root);
  }
}
5 7 9 1 4 3

જટિલતા વિશ્લેષણ

સમય જટિલતા

ઓ (એન), કારણ કે આપણે ઝાડના બધા ગાંઠોમાંથી પસાર થઈ ગયા છે. જ્યારે આપણે પ્રિંટલેફ્ટ, પ્રિન્ટરાઇટ અને પ્રિંટલેવ ફંક્શનનો ઉપયોગ કરીએ છીએ ત્યારે અમે ગાંઠોમાંથી પસાર થઈએ છીએ. આમ સમય જટિલતા રેખીય છે.

અવકાશ જટિલતા

ઓ (એચ), જ્યાં H એ ઝાડની heightંચાઈ છે. આ કારણ છે કે કમ્પાઇલર સ્ટેક જગ્યાનો ઉપયોગ કરે છે. અને સીમા તત્વોને છાપવા માટે ઉપયોગમાં લેવામાં આવતા કાર્યો રિકર્ઝનનો ઉપયોગ કરે છે જે કમ્પાઇલર સ્ટેકની ગણતરી કરે છે.