బైనరీ చెట్టు యొక్క వికర్ణ ట్రావెర్సల్


కఠినత స్థాయి మీడియం
తరచుగా అడుగుతుంది అమెజాన్ ఫాక్ట్‌సెట్ ఇష్టపడేవారిని ఫోర్కైట్స్ ఒరాకిల్ PayU కోరా
బైనరీ చెట్టు ట్రీ చెట్టు ట్రావెర్సల్

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

“బైనరీ ట్రీ యొక్క వికర్ణ ట్రావెర్సల్” సమస్య మీకు బైనరీ చెట్టు ఇవ్వబడిందని మరియు ఇప్పుడు మీరు ఇచ్చిన చెట్టుకు వికర్ణ వీక్షణను కనుగొనవలసి ఉందని పేర్కొంది. మేము ఎగువ-కుడి దిశ నుండి ఒక చెట్టును చూసినప్పుడు. మనకు కనిపించే నోడ్లు బైనరీ చెట్టు యొక్క వికర్ణ వీక్షణ.

ఉదాహరణ

బైనరీ చెట్టు యొక్క వికర్ణ ట్రావెర్సల్

2 7
3 4
5 6

వివరణ

మొదటి వికర్ణంలో నోడ్స్ 2, 7 ఉన్నాయి. అప్పుడు రెండవ వికర్ణానికి 3, 4 ఉంటుంది, అదే విధంగా మూడవ వికర్ణ 5, 6 కు ఉంటుంది. ఈ విధంగా అవుట్పుట్ ఒకే వికర్ణంలోని మూలకాలు ఒకే వరుసలో ఉండే విధంగా ముద్రించబడతాయి.

అప్రోచ్

బైనరీ చెట్టు యొక్క వికర్ణ ట్రావెర్సల్

ఎగువ-కుడి దిశ నుండి మనకు కనిపించే నోడ్‌లను ముద్రించమని సమస్య అడుగుతుంది. కాబట్టి మేము సమస్యను ఎలా పరిష్కరించగలం?

మేము బైనరీ చెట్టు యొక్క క్రమరహిత ట్రావెర్సల్ చేస్తాము. ఇలా చేస్తున్నప్పుడు, దూరాన్ని వికర్ణ దిశలో ఉంచుతాము. మేము ఎడమ దిశలో కదిలినప్పుడల్లా వికర్ణ దూరానికి 1 ని జోడిస్తాము మరియు మనం సరైన దిశలో కదిలితే దూరానికి ఎటువంటి విలువను జోడించము. కాబట్టి, ఇలా చేస్తున్నప్పుడు మేము a లో సందర్శించిన నోడ్‌లను ట్రాక్ చేస్తాము చిహ్నం. మేము వికర్ణ దూరాన్ని కీగా మరియు వెక్టర్‌ను విలువగా రూపొందిస్తాము. ఎందుకంటే మేము వెక్టర్‌లో వికర్ణ దూరంతో నోడ్‌లను జోడిస్తాము. మరియు మేము మొత్తం గుండా ప్రయాణించాము చెట్టు. ట్రావెర్సల్ తరువాత, మేము నోడ్లను వారి వికర్ణ దూరం ప్రకారం వెక్టర్లలో ఉంచాము.

ఈ అన్ని లెక్కల తరువాత, ప్రతి వెక్టర్స్ నుండి నోడ్లను వేరుచేసేటప్పుడు మ్యాప్‌లోని మూలకాలను ముద్రించండి.

బైనరీ ట్రీ యొక్క వికర్ణ ట్రావెర్సల్‌ను ముద్రించడానికి సి ++ కోడ్

#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;
}

void diagonalView(node* root, int dis, map<int, vector<int>> &m){
    if(root){
        m[dis].push_back(root->data);
        // move in the left direction with dis+1 distance
        diagonalView(root->left, dis+1, m);
        // move in the right direction with dis distance
        diagonalView(root->right, dis, m);
    }
}

int main(){
    node *root = create(2);
    root->left = create(3);
    root->right = create(7);
    root->left->left = create(5);
    root->left->right = create(4);
    root->left->right->left = create(6);

    map<int, vector<int>> m;
    diagonalView(root, 0, m);
    for(auto x: m){
        for(auto nodes: x.second)
            cout<<nodes<<" ";
        cout<<endl;
    }
}
2 7
3 4
5 6

బైనరీ ట్రీ యొక్క వికర్ణ ట్రావెర్సల్‌ను ముద్రించడానికి జావా కోడ్

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 void diagonalView(node root, int dis, Map<Integer, Vector<Integer>> m){
      if(root != null){
      	Vector<Integer> v = m.get(dis);
      	if(v == null){
      		v = new Vector<Integer>();
      		v.add(root.data);
      	}
      	else
      		v.add(root.data);
          m.put(dis, v);
          // move in the left direction with dis+1 distance
          diagonalView(root.left, dis+1, m);
          // move in the right direction with dis distance
          diagonalView(root.right, dis, m);
      }
  }

  public static void main(String[] args){
    node root = create(2);
      root.left = create(3);
      root.right = create(7);
      root.left.left = create(5);
      root.left.right = create(4);
      root.left.right.left = create(6);

      Map<Integer, Vector<Integer>> m = new TreeMap<Integer, Vector<Integer>>();
      diagonalView(root, 0, m);
      for(Map.Entry<Integer, Vector<Integer>> entry : m.entrySet())
          System.out.println(entry.getValue());
  }
}
[2, 7]
[3, 4]
[5, 6]

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

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

O (NlogN), ఎందుకంటే మేము చెట్టును దాటి, విలువలను నవీకరించాము. మేము మ్యాప్‌ను ఉపయోగించినందున, చొప్పించడం, తొలగించడం మరియు శోధించడం O (logN) సమయంలో జరుగుతుంది.

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

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