اینری ٹری میں دیئے ہوئے نوڈ کے بہن بھائیوں کی تعداد


مشکل سطح ہارڈ
اکثر پوچھا جاتا ہے ایمیزون بلومبرگ کوڈ نیشن گوگل
N-ary-درخت قطار تلاش درخت درخت ٹراورسال

مسئلہ یہ بیان

مسئلہ "اینری ٹری میں دیئے ہوئے نوڈ کے بہن بھائیوں کی تعداد" یہ بتاتا ہے کہ آپ کو این آرری ٹری اور ٹارگٹ نوڈ دیا جاتا ہے۔ ہدف نوڈ کے بہن بھائیوں کی تعداد تلاش کریں۔ فرض کریں کہ نوڈ ہمیشہ درخت میں موجود ہوتا ہے اور پہلا نوڈ درخت کی جڑ ہوتا ہے۔

مثال کے طور پر

ان پٹ

اینری ٹری میں دیئے ہوئے نوڈ کے بہن بھائیوں کی تعداد

نوڈ = 10
نوڈ = 11

3
1

وضاحت
10 کے بہن بھائی 41 ، 6 ، 32 are ہیں
11 کے بہن بھائی 9} ہیں

الگورتھم

نوڈ کے بہن بھائی ایک نوڈ ہوتے ہیں جس طرح دیئے گئے نوڈ کی طرح ہوتے ہیں ، یا دوسرے لفظوں میں نوڈ کے بہن بھائی اس کے والدین کے بچوں کی تعداد سے کم ہوتے ہیں۔

ذرا درخت مندرجہ بالا مثال میں ، اور نوڈ کو 10 ہونے دیں
10 = 51 کا والدین
51 کے بچے 10 {، 41 ، 32 ، 6 are ہیں
10 کے بہن بھائی اس کے والدین کے بچے ہیں سوائے 10 کے ، یعنی 10 کے بہن بھائی 41 ، 32 ، 6} ہیں

اہم نکتہ: جڑ کے بہن بھائیوں کی تعداد 0 ہے۔ کیوں کہ جڑوں کے والدین نہیں ہیں۔

نوڈ کے بہن بھائیوں کی تعداد تلاش کرنے کا خیال یہ ہے کہ دیئے گئے درخت پر بی ایف ایس کریں ، اگر نوڈ کے بچے دیئے گئے نوڈ کی طرح ہی ہوں تو واپسی (اس نوڈ کے بچوں کی تعداد - 1)۔

  1. اگر دیئے گئے نوڈ جڑ کے برابر ہوں یا روٹ ناخن ہے تو ، 0 واپس کریں۔
  2. کے لئے نوڈس کی قطار بنائیں بییفایس اور جڑ کو قطار میں دھکیل دیں۔
  3. جبکہ قطار خالی نہیں ہے 4 قدم XNUMX۔
  4. کسی عنصر کو قطار سے ہٹائیں ، موجودہ عنصر کے سارے بچوں سے گزریں ، اگر اس کا کوئی بچہ دیئے گئے نوڈ کے برابر ہے تو واپس آجائیں ، (موجودہ نوڈ کے بچوں کی تعداد - 1) ، بصورت دیگر بچوں کو قطار میں کھینچیں۔
  5. اگر دیئے گئے نوڈ سے مماثل کوئی نوڈ نہیں ہے تو ، -1 واپس کریں۔

ضابطے

جاوا کوڈ اینری کے درخت میں دیئے گئے نوڈ کے بہن بھائیوں کی تعداد تلاش کرنے کے لئے

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;

class NumberOfSiblingsOfAGivenNodeInNAryTree {
    // class representing node of n-ary tree
    static class Node {
        
        ArrayList<Node> child;
        int data;
        public Node(int data) {
            this.data = data;
            this.child = new ArrayList<>();
        }
    }

    private static int siblings(Node root, int target) {
        // if the given node is equals to the root or root is null, return 0
        if (root == null || root.data == target) {
            return 0;
        }

        // create a queue of nodes
        Queue<Node> queue = new LinkedList<>();
        // push the root to queue
        queue.add(root);

        // do a BFS of the tree
        while (!queue.isEmpty()) {
            // remove one element from the queue
            Node curr = queue.poll();
            // traverse its children
            for (int i = 0; i < curr.child.size(); i++) {
                // current child
                Node currChild = curr.child.get(i);
                // if current child is the target, return (parent's children count - 1)
                if (currChild.data == target) {
                    return (curr.child.size() - 1);
                }
                // add the child to the queue
                queue.add(currChild);
            }
        }

        // if there is no match, return -1
        return -1;
    }

    public static void main(String[] args) {
        // Example n-ary tree
        Node root = new Node(51);
        // children of 51
        root.child.add(new Node(10));
        root.child.add(new Node(41));
        root.child.add(new Node(6));
        root.child.add(new Node(32));
        // children of 10
        root.child.get(0).child.add(new Node(53));
        // children of 41
        root.child.get(1).child.add(new Node(95));
        // children of 6
        root.child.get(2).child.add(new Node(28));
        // children of 32
        root.child.get(3).child.add(new Node(9));
        root.child.get(3).child.add(new Node(11));
        // children of 53
        root.child.get(0).child.get(0).child.add(new Node(5));
        root.child.get(0).child.get(0).child.add(new Node(7));
        // children of 11
        root.child.get(3).child.get(1).child.add(new Node(3));
        root.child.get(3).child.get(1).child.add(new Node(8));

        System.out.println(siblings(root, 10));
        System.out.println(siblings(root, 11));
    }
}
3
1

این + ایری ٹری میں دیئے ہوئے نوڈ کے بہن بھائیوں کی تعداد تلاش کرنے کے لئے C ++ کوڈ

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

// class representing node of a n-ary tree
class Node {
    public:
    int data;
    vector<Node*> child;
    
    Node(int d) {
        data = d;
    }
};

int siblings(Node *root, int target) {
    // if the given node is equals to the root or root is null, return 0
    if (root == NULL || root->data == target) {
        return 0;
    }
    
    // create a queue of nodes
    queue<Node*> q;
    // push the root to queue
    q.push(root);
    
    // do a BFS of the tree
    while (!q.empty()) {
        // remove one element from the queue
        Node *curr = q.front();
        q.pop();
        // traverse its children
        for (int i = 0; i < curr->child.size(); i++) {
            // current child
            Node *currChild = curr->child[i];
            // if current child is the target, return (parent's children count - 1)
            if (currChild->data == target) {
                return (curr->child.size() - 1);
            }
            // add the child to the queue
            q.push(curr->child[i]);
        }
    }
    
    // if there is no match, return -1
    return -1;
}

int main() {
    // Example n-ary tree
    Node *root = new Node(51);
    // children of 51
    root->child.push_back(new Node(10));
    root->child.push_back(new Node(41));
    root->child.push_back(new Node(6));
    root->child.push_back(new Node(32));
    // children of 10
    root->child[0]->child.push_back(new Node(53));
    // children of 41
    root->child[1]->child.push_back(new Node(95));
    // children of 6
    root->child[2]->child.push_back(new Node(28));
    // children of 32
    root->child[3]->child.push_back(new Node(9));
    root->child[3]->child.push_back(new Node(11));
    // children of 53
    root->child[0]->child[0]->child.push_back(new Node(5));
    root->child[0]->child[0]->child.push_back(new Node(7));
    // children of 11
    root->child[3]->child[1]->child.push_back(new Node(3));
    root->child[3]->child[1]->child.push_back(new Node(8));

    cout<<siblings(root, 10)<<endl;
    cout<<siblings(root, 11)<<endl;
    
    return 0;
}
3
1

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

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

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

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

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