بائنری ٹری کی باؤنڈری ٹراورسال


مشکل سطح درمیانہ
اکثر پوچھا جاتا ہے اکٹھا کرنا ایمیزون اضافہ Kritikal حل مائیکروسافٹ مارگن سٹینلی پی پی یو Snapdeal
ثنائی درخت درخت درخت ٹراورسال

مسئلہ یہ بیان

مسئلہ "بائنری ٹری کی باؤنڈری ٹراورسل" یہ بتاتا ہے کہ آپ کو بائنری ٹری دیا گیا ہے۔ اب آپ کو a کا باؤنڈری ویو پرنٹ کرنے کی ضرورت ہے بائنری ٹری. یہاں حد عبور کا مطلب یہ ہے کہ تمام نوڈس کو درخت کی حد کے طور پر دکھایا گیا ہے۔ گھڑی کی مخالف سمت میں نوڈس کو اوپر کی طرف ، بائیں جانب ، نیچے کی طرف اور دائیں جانب سے دیکھا جاتا ہے۔ لیکن اگر ہم ان تمام ملاحظات کو براہ راست پرنٹ کرتے ، جس کے نتیجے میں ایک ہی نوڈس کو متعدد بار چھاپنا پڑتا ہے۔ تو حد نگاہ کو اس طرح پرنٹ کریں کہ نوڈس کو دہرایا نہیں جائے۔

مثال کے طور پر

2 3 5 6 4 7

وضاحت

یہاں ، تمام نوڈس باؤنڈری نوڈس ہیں۔ لیکن ہمیں نوٹوں کو گھڑی مخالف سمت میں پرنٹ کرنے کی ضرورت ہے۔ اس طرح ہم 2 سے جڑ سے شروع کرتے ہیں۔ پھر ، ہم صرف اسی انداز میں آگے بڑھتے ہیں اور نوڈس 2 ، 3 ، 4 ، 6 ، 4 ، 7 پرنٹ کرتے ہیں۔

بائنری ٹری کی باؤنڈری ٹراورسال

5 7 9 1 4 3

نقطہ نظر

مسئلہ ہم سے درخت کی حد پرنٹ کرنے کو کہتا ہے ، یہاں ہم نے بائیں ، دائیں اور نیچے کی حد بندی کردی ہے۔ اگر درخت کی بائیں اور دائیں حد نہیں ہوتی ہے۔ جڑ کو ہی بائیں یا دائیں حد کے طور پر سمجھا جاتا ہے۔ ایک شرط یہ بھی ہے کہ اگر ہم باؤنڈری نوڈس پرنٹ کرتے ہیں تو ہمیں اس بات کا خیال رکھنا ہوگا کہ دونوں نوڈس میں سے کوئی بھی متعدد بار پرنٹ نہ ہو۔

مسئلے کو حل کرنے کے لئے ، ہم درخت کی بائیں بازو سے شروع کریں گے۔ ہم کہتے ہیں کہ اگر نوڈ بائیں طرف سے دکھائی دیتا ہے تو نوڈ بائیں باؤنڈری سے تعلق رکھتا ہے۔ اسی طرح ، ہم دائیں طرف کے نوڈس اور پتی کے نوڈس کی وضاحت کرتے ہیں۔ بائیں باؤنڈری کو پرنٹ کرنے کے ل we ، ہم درخت کو اس طرح سے عبور کریں گے کہ اگر جڑ کا ایک بائیں نوڈ ہے تو پھر اس کے دائیں نوڈ میں منتقل ہوجائیں۔ ایک بار جب ہم پتی کے نوڈ پر پہنچ جائیں گے۔ ہم لیف نوڈس پرنٹ نہیں کرتے ہیں کیونکہ ہم لفٹ نوٹوں کو الگ الگ پرنٹ کرتے ہیں۔ ایک بار جب ہم بائیں باؤنڈری کے ساتھ ہوجاتے ہیں۔

ہم بار بار سب سے پہلے بائیں ذیلی درختوں کی پرنٹ کرکے پتی کے نوڈس پرنٹ کرتے ہیں۔ بائیں سب ٹری پرنٹ کرنے کے بعد پتے دائیں سب ٹری میں پرنٹ کریں۔ اس طرح سارے لیف نوڈس گھڑی کی مخالف سمت میں چھاپیں گے۔ ایک بار جب ہم پتے پرنٹ کرتے ہیں تو ، ہم دائیں حد کے نوڈس کو پرنٹ کرتے ہیں۔ اس بار نوڈس کو نیچے والے انداز میں پرنٹ کرنے کی ضرورت ہے۔ اس طرح کے اندر تکرار، پہلے ہم درخت کے بائیں یا دائیں سب ٹری کو حل کرتے ہیں اور پھر موجودہ نوڈ کو مکسرنٹ کریں۔

بائنری ٹری کی باؤنڈری ٹراورسال پرنٹ کرنے کے لئے C ++ کوڈ

#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

پیچیدگی کا تجزیہ

وقت کی پیچیدگی

O (N) ، کیونکہ ہم درخت کے تمام نوڈس سے گزر چکے ہیں۔ جب ہم پرنٹ لیفٹ ، پرنٹ رائٹ اور پرنٹ لیو فنکشن کا استعمال کرتے ہیں تو ہم نوڈس سے گزر جاتے ہیں۔ اس طرح وقت کی پیچیدگی لکیری ہے۔

خلائی پیچیدگی

O (H) ، جہاں H درخت کی اونچائی ہے۔ اس کی وجہ یہ ہے کہ مرتب کرنے والا اسٹیک جگہ استعمال کرتا ہے۔ اور حدود عناصر کی پرنٹ کرنے کے لئے استعمال ہونے والے افعال تکرار کا استعمال کرتے ہیں جو مرتب کرنے والے اسٹیک کے حساب سے ہیں۔