بائنري سرچ وڻ تي ليٽ ڪوڊ جو حل ڳوليو


تڪليف جي سطح آسان
بار بار پڇڻ ۾ ايپل IBM
ثنائي ڳولا وارو وڻ

انهي مسئلي ۾ ، اسان هڪ ڏني وئي آهي ثنائي ڳولا وارو وڻ ۽ هڪ صحيح اسان کي ساڳيو عدد جي جيتري قدر سان هڪ نوڊ جو پتو ڳولڻ گهرجي. هڪ چيڪ جي طور تي ، اسان کي ذيلي وڻ جو پريڊر ٽراؤزر پرنٽ ڪرڻ جي ضرورت آهي جيڪا هن نوڊ کي روٽ وانگر آهي. جيڪڏهن وڻ ۾ ڏنل انگيز جيتري قدر ناهي ، اسان کي واپس ٿيڻ جي ضرورت آهي NULL، يعني خالي وڻ.

مثال

     2
    
  /     \

1         3

             \

               4


Target Value = 3
3 4
     5

  /      \

1         10 


Target Value = 4
Empty BST

وضاحت # 1

بي ايس ٽي 3 سان گڏ هڪ نوڊ تي مشتمل آھي ، تنھنڪري اسين ان جو ذيلي وڻ واپس آڻيندا آھيون ۽ ان جي پريڊروزر ٽراسل کي پرنٽ ڪريون ٿا

وضاحت # 2

بي ايس ٽي قيمت 4 ۾ ڪو به نوڊ شامل ناهي ، ان ڪري اسان نالا موٽايو ۽ ”خالي بي ايس ٽي“ پرنٽ ڪيو.

رستو (ٻيهر ورجائي)

اسان کي سوچڻ ڏي ته ڪيئن هڪ ڪيس هن صورت ۾ ذيلي مسئلن تي منحصر آهي. اچو ته چوندا آهن ته اسان جو فنڪشن نوڊ جي ايڊريس کي ٽارگيٽ ويليو سان موٽائيندو آهي ، جيڪڏهن مليو. اسان وڻ جي پاڙ مان شروع ڪريون ٿا. جيڪڏھن اھو نوڊ آھي نول ، ظاهر آهي اسان بائنري سرچ وڻ جي آخر ۾ پهچي چڪا آهيون ۽ ان ڪري ٽارگيٽ ويليو سان ڪو به نوڊ ناهي. تنهن ڪري ، اسان موٽون ٿا نول. ساڳي طرح ، اسان نوڊ قدر حدف جي قيمت جي برابر آهي ، اسين هي نوڊ واپس ڪريون ٿا. ٻي صورت ۾ ، اسان knowاڻون ٿا ته ٽارگيٽ ويلڊ نوڊ يا ته ٿيندو کاٻو ذيلي يا ساڄو موجوده روٽ جو ذيلي وڻ. اسان root.value ۽ ٽارگيٽ ويليو جو مقابلو ڪري اسان طرف (کاٻي يا سا )ي) فيصلو ڪري سگهون ٿا. تنهن ڪري ، اسان انهي سان ٻيهر ٻيهر هلندڙ فنڪشن کي سڏيندا آهيون پاڙ as root.ft or root.right.

بائنري سرچ وڻ تي ليٽ ڪوڊ جو حل ڳوليو

الورورٿم

  1. ڪم ٺاهيو سرچ BST () ٽارگيٽ ايڊريس واپس ڪرڻ
  2. If پاڙ جي برابر آهي اجايو OR پاڙ ساڳي قيمت حدف جي مقابلي ۾ آهي
    • روٽ موٽڻ
  3. جيڪڏهن روٽ ويليو ٽارگيٽ ويليو کان وڌيڪ آهي:
    1. موٽڻ سرچ BST (root.left ، val)
  4. واپسي سرچ BST (root.right، val)
  5. حدف ٿيل نوڊ جي پري آرڊر پيچرو کي پرنٽ ڪيو

بائنري سرچ وڻ Leetcode حل ۾ ڳولا جو عمل

سي ++ پروگرام

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

struct BSTNode
{
    int value;
    BSTNode *left , *right;
    BSTNode(int val)
    {
        value = val;
        left = right = NULL;
    }
};

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

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

int main()
{
    BSTNode* root = new BSTNode(2);
    root->left = new BSTNode(1);
    root->right = new BSTNode(3);
    root->right->right = new BSTNode(4);
    int val = 3;
    BSTNode* targetNode = searchBST(root , val);
    if(targetNode == NULL)
    {
        cout << "Empty Tree" << '\n';
        return 0;
    }
    preorderTraversal(targetNode);
    return 0;
}

جاوا پروگرام

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

class search_in_BST
{
    public static void main(String args[])
    {
        BSTNode root = new BSTNode(2);
        root.left = new BSTNode(1);
        root.right = new BSTNode(3);
        root.right.right = new BSTNode(4);
        int val = 3;
        BSTNode targetNode = searchBST(root , val);
        if(targetNode == null)
        {
            System.out.println("Empty Tree");
            System.exit(0);
        }
        preorderTraversal(targetNode);
    }

    static BSTNode searchBST(BSTNode root , int val)
    {
        if(root == null)
            return root;
        if(val == root.value)
            return root;
        if(val < root.value)
            return searchBST(root.left , val);
        return searchBST(root.right , val);
    }

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

بائنري سرچ وڻ ليٽ ڪوڊ حل ۾ ڳولا جي پيچيدگي تجزيه

وقت جي پيچيدگي

اي (ايڇ) ، ايڇ = لاگ اين = سراسري ڪيسن ۾ BST جي اوچائي ۽ اي (اين) ، اين = بدترين ڪيسن ۾ بي ايس ٽي جو سائز. اسان هڪ ڀيرو بدترين حالتن ۾ وڻ کي ٽوڙيو ٿا جيڪو ٿئي ٿو جڏهن بي ايس ٽي اونچائي تي ڪئي وئي آهي.

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

اي (ايڇ) عام صورتن ۾ ، هر نوڊ مان لنگھڻ لاءِ اسان Recursive Call استعمال ڪندا آھيون. اي (اين) بدترين حالت ۾. هڪ اهم ياد اهو آهي ته ڪجهه ساز ترتيب ڏيڻ وارا پڇو ۽ انهن حالتن ۾ ، خلائي پيچيدگي ٿي ويندي آهي اي (1).

رستو (ٻيهر ورجائي)

مٿين طريقي سان ملندڙ ، اسين ڇڏي وڃو سا leftي يا کاٻي وreeي جيڪڏهن ٽارگيٽ ويليو موجوده نوڊ ۾ موجود نه آهي ، اسان انهي کي ترتيب ڏيندي ٻرڙو ڪري سگھون ٿا root = root.left or root = root. صحيح هر پهاڙ تي ، جيستائين روٽ نه بڻجي وڃي خالي جيڪڏهن اسان اهو معلوم ڪيو ته روٽ جي قيمت ڪنهن تعريف ۾ ٽارگيٽ ويليو جي برابر آهي. ٻي صورت ۾ ، اسان موٽون ٿا خالي

الورورٿم

  1. ساڳيو ڪم ٺاهيو سرچ BST () اھو ٽارگيٽ نوڊ جو پتو موٽائي ٿو
  2. جڏهن ته پاڙ is نه خالي:
    • if root.value برابر قيمت جي برابر آهي
      • موٽڻ پاڙ
    • if root.val is تمام وڏو حد کان وڌيڪ قدر
      • ھيٺ ڏنل سبجيڪٽ ڏانھن وڃو root = root. صحيح
    • هم عصر
      • کاٻي tيري کي منتقل ڪريو جيئن: root = root.left
  3. واپسي اجايو
  4. حدف ٿيل نوڊ جي پري آرڊر پيچرو کي پرنٽ ڪيو

بائنري سرچ وڻ Leetcode حل ۾ ڳولا جو عمل

سي ++ پروگرام

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

struct BSTNode
{
    int value;
    BSTNode *left , *right;
    BSTNode(int val)
    {
        value = val;
        left = right = NULL;
    }
};

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

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

int main()
{
    BSTNode* root = new BSTNode(2);
    root->left = new BSTNode(1);
    root->right = new BSTNode(3);
    root->right->right = new BSTNode(4);
    int val = 3;
    BSTNode* targetNode = searchBST(root , val);
    if(targetNode == NULL)
    {
        cout << "Empty Tree" << '\n';
        return 0;
    }
    preorderTraversal(targetNode);
    return 0;
}

جاوا پروگرام

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

class search_in_BST
{
    public static void main(String args[])
    {
        BSTNode root = new BSTNode(2);
        root.left = new BSTNode(1);
        root.right = new BSTNode(3);
        root.right.right = new BSTNode(4);
        int val = 3;
        BSTNode targetNode = searchBST(root , val);
        if(targetNode == null)
        {
            System.out.println("Empty Tree");
            System.exit(0);
        }
        preorderTraversal(targetNode);
    }

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

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

بائنري سرچ وڻ ليٽ ڪوڊ حل ۾ ڳولا جي پيچيدگي تجزيه

وقت جي پيچيدگي

اي (ايڇ = لاگ اين) سراسري ڪيسن ۾ ۽ اي (اين) بدترين ڪيسن ۾ (Bاٿل BST) ، ساڳي طريقي سان ساڳيو.

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

اي (1) جئين اسان صرف مسلسل يادگيري جي جڳهه استعمال ڪندا آهيون.