బైనరీ సెర్చ్ ట్రీ లీట్‌కోడ్ సొల్యూషన్‌లోకి చొప్పించండి


కఠినత స్థాయి మీడియం
తరచుగా అడుగుతుంది అమెజాన్ ఆపిల్ Atlassian <span style="font-family: Mandali; ">ఫేస్‌బుక్ </span> గూగుల్ మైక్రోసాఫ్ట్
బైనరీ శోధన చెట్టు

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

ఉదాహరణ

Binary Search Tree:
 
    7
 
  /     \

3         10

        /

      8
Integer Value = 11
3 7 8 10 11
Binary Search Tree:
           5

         /

       4

     /

   3
Integer Value = 2
2 3 4 5

వివరణ

బైనరీ సెర్చ్ ట్రీ లీట్‌కోడ్ సొల్యూషన్‌లోకి చొప్పించండి

బైనరీ సెర్చ్ ట్రీ లీట్‌కోడ్ సొల్యూషన్‌లోకి చొప్పించండి

అప్రోచ్ (రికర్సివ్)

మా బైనరీ సెర్చ్ ట్రీలో ఏదైనా నోడ్ ఎక్కడ చేర్చాలో నిర్ణయించడానికి, మేము రూట్ నుండి సంబంధిత నోడ్‌కు ఒక మార్గాన్ని సెటప్ చేయాలి, దీని ఎడమ / కుడి బిడ్డ ఇచ్చిన నోడ్ అవుతుంది.

పనిని సమస్య నుండి దాని ఉప సమస్యకు పంపించడం ద్వారా మనం దీన్ని పునరావృతంగా పరిష్కరించవచ్చు. ఈ సందర్భంలో, ఒక చెట్టులోకి కొత్త నోడ్‌ను చొప్పించడం అంటే దాని ఎడమ సబ్‌ట్రీ లేదా కుడి సబ్‌ట్రీకి చొప్పించడం. ఇదే ఆలోచన ఇంకేమైనా సబ్‌ట్రీలకు కూడా ఉంటుంది. మేము బేస్ కేసును ఏర్పాటు చేయాలి. ఏదైనా సబ్‌ట్రీ యొక్క రూట్ నోడ్ ఉన్న చోటికి చేరుకున్నప్పుడు NULL, లక్ష్య నోడ్‌ను చొప్పించడానికి మేము మార్గం చివరికి చేరుకున్నామని దీని అర్థం. కాబట్టి, మేము తిరిగి వస్తాము కొత్త ఇచ్చిన విలువగా నోడ్ విలువను కలిగి ఉన్న నోడ్ చిరునామా. ఏదైనా ఏకపక్ష మూలకం కోసం శోధించడానికి బైనరీ శోధన చెట్లకు గణనీయమైన ప్రయోజనం ఉంది O (logN) సగటు కేసులలో సమయం. కాబట్టి, ఈ సందర్భంలో, క్రొత్త నోడ్ యొక్క స్థానం సమర్థవంతమైన సమయంలో చేర్చబడాలని మేము కనుగొన్నాము.

అల్గారిథం

  1. ఒక ఫంక్షన్ సృష్టించండి insertIntoBST () ఇది చిరునామాను తిరిగి ఇస్తుంది రూట్ ఇచ్చిన వాటిని చేర్చిన తరువాత BST నోడ్
  2. insertIntoBST () రెండు పారామితులను కలిగి ఉంది: రూట్ చెట్టు మరియు విలువ చేర్చవలసిన నోడ్ యొక్క
  3. ఫంక్షన్ ఈ క్రింది వాటిని చేస్తుంది:
    • If రూట్ is శూన్య ఇచ్చిన విలువకు సమానమైన విలువతో క్రొత్త ట్రీ నోడ్‌ను తిరిగి ఇవ్వండి
    • ఇచ్చిన విలువ ఉంటే ఎక్కువ విలువ కంటే రూట్ నోడ్, ఆపై అదే సమస్యను కుడి సబ్‌ట్రీకి కాల్ చేసి, ఆపై రూట్‌ని తిరిగి ఇవ్వండి
      • root.right = insertIntoBST (root-> కుడి, విలువ)
      • తిరిగి రూట్
    • ఎడమ సబ్‌ట్రీలో ఇతర శోధన ఇలా:
      • root.left= insertIntoBST (root.left, విలువ)
      • తిరిగి రూట్
  4. బైనరీ సెర్చ్ ట్రీ యొక్క ఇనార్డర్ ట్రావెర్సల్‌ను ప్రింట్ చేయండి

బైనరీ సెర్చ్ ట్రీ లీట్‌కోడ్ సొల్యూషన్‌లో చొప్పించడం అమలు

సి ++ ప్రోగ్రామ్

#include <bits/stdc++.h>
using namespace std;
struct BSTNode
{
    int value;
    BSTNode *left , *right;
    BSTNode(int x)
    {
        value = x;
        left = NULL;
        right = NULL;
    }
};

void inorderTraversal(BSTNode* root)
{
    if(root == NULL)
        return;
    inorderTraversal(root->left);
    cout << root->value << " ";
    inorderTraversal(root->right);
    return;
}


BSTNode* insertIntoBST(BSTNode* root , int val)
{
    if(root == NULL)
        return new BSTNode(val);
    if(val > root->value)
    {
        root->right = insertIntoBST(root->right , val);
        return root;
    }
    root->left = insertIntoBST(root->left , val);
    return root;
}

int main()
{
    BSTNode* root = new BSTNode(7);
    root->left = new BSTNode(3);
    root->right = new BSTNode(10);
    root->right->left = new BSTNode(8);
    int val = 11;
    root = insertIntoBST(root , val);
    inorderTraversal(root);
    return 0;
}

జావా ప్రోగ్రామ్

class BSTNode
{
    int value;
    BSTNode left , right;

    BSTNode(int val)
    {
        value = val;
        left = right = null;
    }
}

class insert_into_BST
{
    public static void main(String args[])
    {
        BSTNode root = new BSTNode(7);
        root.left = new BSTNode(3);
        root.right = new BSTNode(10);
        root.right.left = new BSTNode(8);
        int val = 11;
        root = insertIntoBST(root , val);
        inorderTraversal(root);
    }

    static BSTNode insertIntoBST(BSTNode root , int val)
    {
        if(root == null)
            return new BSTNode(val);
        if(val > root.value)
        {
            root.right = insertIntoBST(root.right , val);
            return root;
        }
        root.left = insertIntoBST(root.left , val);
        return root;
    }

    static void inorderTraversal(BSTNode root)
    {
        if(root == null)
            return;
        inorderTraversal(root.left);
        System.out.print(root.value + " ");
        inorderTraversal(root.right);
        return;
    }
}

3 7 8 10 11

బైనరీ సెర్చ్ ట్రీ లీట్‌కోడ్ సొల్యూషన్‌లోకి చొప్పించడం యొక్క సంక్లిష్టత విశ్లేషణ

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

ఓ (హెచ్) = BST యొక్క ఎత్తు = logN (ఇక్కడ BST లో N = సంఖ్యల సంఖ్య) సగటు సందర్భాల్లో (మేము లాగ్ఎన్ పునరావృత కాల్స్ చేస్తున్నప్పుడు). కానీ పై) చెట్టు వక్రంగా ఉన్నప్పుడు చెత్త సందర్భంలో. ఒకవేళ చెట్టు వక్రంగా ఉంటే, శోధన a అవుతుంది సరళ ఒకటి.

స్థల సంక్లిష్టత

ఓ (హెచ్) సగటు సందర్భాల్లో. పై) చెత్త సందర్భంలో. స్పేస్ కాంప్లెక్సిటీ విషయంలో ఇక్కడ టైమ్ కాంప్లెక్సిటీ మాదిరిగానే ఉంటుంది, ఎందుకంటే ఇది మేము చేసే పునరావృత కాల్‌ల సంఖ్యపై ఆధారపడి ఉంటుంది.

అప్రోచ్ (పునరుక్తి)

స్థల సంక్లిష్టతను మెరుగుపరచడానికి మేము పై విధానాన్ని పునరావృతంగా అనుసరించవచ్చు. పునరావృతం మెమరీని వినియోగించే స్టాక్ ఫ్రేమ్‌లను ఉపయోగిస్తుంది. కాబట్టి, పునరుత్పాదక ద్రావణంలో, మేము నిరోధించాము పునరావృత కాల్ లోడ్ మరియు ఎడమ లేదా కుడి వైపున ఉన్న నోడ్‌ను కొట్టే వరకు మా శోధన మార్గంలో చెట్టుపైకి వెళ్ళండి NULL. మేము ఉన్నప్పుడు root.left / root.right = NULL, మేము ఈ నోడ్‌ను ఇచ్చిన విలువకు సమానమైన విలువతో క్రొత్త నోడ్‌కు సమానంగా సెట్ చేస్తాము. విలువలను పోల్చడం ద్వారా మేము మార్గాన్ని నిర్ణయిస్తాము రూట్ ప్రతి పునరావృత కాల్‌లో విలువ.

అల్గారిథం

  1. మేము మళ్ళీ ఒక insertIntoBST () పైన పేర్కొన్న అదే ప్రయోజనం కోసం
  2. అయితే రూట్ NULL
    1. ఇచ్చిన విలువకు సమానమైన విలువతో కొత్త నోడ్‌ను తిరిగి ఇవ్వండి
  3. రూట్ కాపీని సృష్టించండి, చెప్పండి నకిలీ BST యొక్క కంటెంట్ను మార్చటానికి
  4. అయితే నకిలీ is కాదు NULL
    1. ఇచ్చిన విలువ కంటే ఎక్కువ ఉంటే root.val
      1. If root.right NULL
        1. root.right = ఇచ్చిన విలువతో కొత్త నోడ్
        2. తిరిగి రూట్
      2. లేకపోతే, సెట్ చేయండి
        1. రూట్ = root.right, కుడి సబ్‌ట్రీకి వెళ్లడానికి
    2. విలువ కంటే తక్కువ లేదా సమానంగా ఉంటే root.val
      1. Root.left NULL అయితే
        1. root.left = ఇచ్చిన విలువతో కొత్త నోడ్
        2. తిరిగి రూట్
      2. లేకపోతే, సెట్ చేయండి
        1. రూట్ = root.left, ఎడమ సబ్‌ట్రీకి దూకడం
  5. BST యొక్క ఇనార్డర్ ట్రావెర్సల్‌ను ముద్రించండి

బైనరీ సెర్చ్ ట్రీ లీట్‌కోడ్ సొల్యూషన్‌లో చొప్పించడం అమలు

సి ++ ప్రోగ్రామ్

#include <bits/stdc++.h>
using namespace std;
struct BSTNode
{
    int value;
    BSTNode *left , *right;
    BSTNode(int x)
    {
        value = x;
        left = NULL;
        right = NULL;
    }
};

void inorderTraversal(BSTNode* root)
{
    if(root == NULL)
        return;
    inorderTraversal(root->left);
    cout << root->value << " ";
    inorderTraversal(root->right);
    return;
}

BSTNode* insertIntoBST(BSTNode* root , int val)
{
    if(root == NULL)
        return new BSTNode(val);
    BSTNode* dummy = root;
    while(dummy != NULL)
    {
        if(val > dummy->value)
        {
            if(dummy->right == NULL)
            {
                dummy->right = new BSTNode(val);
                return root;
            }
            else
                dummy = dummy->right;
        }
        else
        {
            if(dummy->left == NULL)
            {
                dummy->left = new BSTNode(val);
                return root;
            }
            else
                dummy = dummy->left;
        }
    }
    return root;
}

int main()
{
    BSTNode* root = new BSTNode(7);
    root->left = new BSTNode(3);
    root->right = new BSTNode(10);
    root->right->left = new BSTNode(8);
    int val = 11;
    root = insertIntoBST(root , val);
    inorderTraversal(root);
    return 0;
}

జావా ప్రోగ్రామ్

class BSTNode
{
    int value;
    BSTNode left , right;

    BSTNode(int val)
    {
        value = val;
        left = right = null;
    }
}

class insert_into_BST
{
    public static void main(String args[])
    {
        BSTNode root = new BSTNode(7);
        root.left = new BSTNode(3);
        root.right = new BSTNode(10);
        root.right.left = new BSTNode(8);
        int val = 11;
        root = insertIntoBST(root , val);
        inorderTraversal(root);
    }

    static BSTNode insertIntoBST(BSTNode root , int val)
    {
        if(root == null)
            return new BSTNode(val);
        BSTNode dummy = root;
        while(dummy != null)
        {
            if(val > dummy.value)
            {
                if(dummy.right == null)
                {
                    dummy.right = new BSTNode(val);
                    return root;
                }
                else
                    dummy = dummy.right;
            }
            else
            {
                if(dummy.left == null)
                {
                    dummy.left = new BSTNode(val);
                    return root;
                }
                else
                    dummy = dummy.left;
            }
        }
        return root;
    }

    static void inorderTraversal(BSTNode root)
    {
        if(root == null)
            return;
        inorderTraversal(root.left);
        System.out.print(root.value + " ");
        inorderTraversal(root.right);
        return;
    }
}

3 7 8 10 11

బైనరీ సెర్చ్ ట్రీ లీట్‌కోడ్ సొల్యూషన్‌లోకి చొప్పించడం యొక్క సంక్లిష్టత విశ్లేషణ

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

ఓ (హెచ్) = BST యొక్క ఎత్తు = logN (ఇక్కడ BST లో N = సంఖ్యల సంఖ్య) సగటు సందర్భాల్లో. కానీ పై) చెట్టు వక్రంగా ఉన్నప్పుడు చెత్త సందర్భంలో. మళ్ళీ, సమయ సంక్లిష్టత గమ్యస్థానానికి చేరుకోవడానికి మనం చేసే పునరావృత సంఖ్యపై ఆధారపడి ఉంటుంది, తరువాత ఇచ్చిన నోడ్ చొప్పించబడాలి మరియు ఇది చెట్టు నిర్మాణంపై ఆధారపడి ఉంటుంది.

స్థల సంక్లిష్టత

O (1). చెత్త సందర్భంలో కూడా, మేము వేరియబుల్స్ కోసం స్థిరమైన స్థలాన్ని మాత్రమే ఉపయోగిస్తాము.