ثنائي وڻ جي وڌ کان وڌ ويڪر


تڪليف جي سطح آسان
بار بار پڇڻ ۾ Amazon سيڊنس انڊيا ڪوپن ڊنيا حقيقت جو جائزو مفت چارج MakeMyTrip جو آهي مونوٽائپ حل اسپيڊل ڪنڊوزس ٽراداتا VMware زو
گہرائي پهرين ڳولا وڻن وڻ ٽرانسورس

مسئلي جو بيان

”بائنري وڻ جي وڌ کان وڌ کوٽائي“ مسئلو ٻڌائي ٿو ته توهان کي بائنري وڻ ڊيٽا جو خاڪو ڏنو ويو آهي. ڏنل جي وڌ کان وڌ کوٽائي بائنري وڻ.

مثال

پٽ

ثنائي وڻ جي وڌ کان وڌ ويڪر

2

وضاحت: ڏنل وڻ جي وڌ ۾ وڌ گہرائي 2. ڇاڪاڻ ته روٽ جي هيٺان هڪڙو واحد عنصر آهي (يعني روٽ ليول کان وڏي گہرائي تي = 1) ٻئي کاٻي ۽ سا subي سبتر ۾.

پٽ

ثنائي وڻ جي وڌ کان وڌ ويڪر

3

وضاحت: ٻه عنصر سطح تي آهن = 3 ، صحيح ماتحت ۾. اھڙي طرح وڌ ۾ وڌ گہرائي = 3.

بائنري وڻ جي وڌ کان وڌ کوٽائي لاءِ الگورٿيم

1. Initialize a binary tree data structure.
2. Create a class node with a variable of integer type and the two-node type pointers left and right as it's private members.
3. Create a function newNode to create a new node of the binary tree which accepts a variable of integer type consisting of data as it's a parameter.
4. After that, initialize a new node inside it. Store the integer variable given as a parameter in the data of the node of the binary tree and update the value of it's left and the right pointer is null.
5. Return the newly created node.
6. Similarly, create a function to find the maximum depth of the binary tree which accepts a node pointer as it's a parameter.
7. Check if the node is equal to null, return 0.
8. Else create a variable left of integer type representing the depth of the left subtree. Make a recursive call to the function itself with the left of the node as it's a parameter and store the result returned in the variable left.
9. Similarly, create a variable right of integer type representing the depth of the right subtree. Make a recursive call to the function itself with the right of the node as it's a parameter and store the result returned in the variable right.
10. After that, check if the depth of the left subtree is greater than the depth of the right subtree return the depth of the left subtree + 1.
11. Else return the variable right i.e. the depth of the right subtree + 1.

هڪ ۾ بائنري وڻ ڊيٽا جو نمونو، اسان وٽ کاٻي ۽ سا nي نوڊيون آهن ، جيڪي پوءِ پاڻ به ڇڏي ويون آهن ۽ سا bodي odesار. ان ڪري ، وڻ وانگر بنا ڊيٽا جي makingانچي. ثنائي وڻ ۾ ، نوڊس سبٽورس ٺاهڻ لاءِ ڳن areيل آهن. تنهن ڪري ، اسان بائنري وڻ ڊيٽا جي جوڙجڪ جي ڪجهه اصطلاحن جي وضاحت ڪيون ٿا. ۽ انهن مان هڪڙو وڌ ۾ وڌ گڻائي آهي ، جنهن جو تعين جڙ کان پتي جي فاصلي تائين وڻ جي وڌ کان وڌ اوچائي. هڪ پتي ڪجهه به ناهي پر هڪ نوڊ آهي جنهن ۾ کاٻي يا سا nي نوڊ نه هجن.

وڌ کان وڌ کوٽائي ڳولڻ لاءِ اسين کاٻي ۽ سا subي سبزي جي کوٽائي کي ڳڻپ ڪريون ٿا. هاڻوڪي وڻ جي کوٽائي وڌ کان وڌ کاٻي ۽ سا subي وڻ جي وڌ کان وڌ برابر آهي +1. اهڙي طرح اسين کاٻي ۽ سا subي سبريٽ جي کوٽائي کي ڳولڻ لاءِ جڙندڙ طريقه ڪار استعمال ڪندا آهيون. جئين اسان تلافي استعمال ڪري رهيا آهيون ، اسان تي ڪجهه بنيادي ڪيس هجڻ گهرجن. هتي بنيادي معاملو اهو آهي جيڪڏهن اسان هڪ نوڊ تي آهيون جيڪا هڪ پتي آهي. پتي جي جوڙ کي ڊگهو آهي = 1.

ڪوڊ

بائنري وڻ جي وڌ کان وڌ کوٽائي ڳولڻ لاءِ C ++ پروگرام

#include <bits/stdc++.h> 
using namespace std; 
  
class node{  
    public: 
        int data;  
        node* left;  
        node* right;  
};  
  
int maxDepth(node* node){  
    if(node == NULL)  
        return 0;  
    else{  
        int left = maxDepth(node->left);  
        int right = maxDepth(node->right);  
      
        if(left > right)  
            return(left + 1);  
        else return(right + 1);  
    }  
}  
  
node* newNode(int data){  
    node* Node = new node(); 
    Node->data = data;  
    Node->left = NULL;  
    Node->right = NULL;  
      
    return(Node);  
}  
      
int main(){  
    node *root = newNode(2);  
  
    root->left = newNode(3);  
    root->right = newNode(8);  
    root->left->left = newNode(6);  
    root->left->right = newNode(9);  
      
    cout<<maxDepth(root);  
    return 0;  
}
3

جاوا پروگرام بائنري وڻ جي وڌ کان وڌ کوٽائي ڳولڻ

class Node{ 
    int data; 
    Node left, right; 
   
    Node(int item){ 
        data = item; 
        left = right = null; 
    } 
} 
   
class BinaryTree{ 
     Node root; 
   
    int maxDepth(Node node){ 
        if(node == null) 
            return 0; 
        else{ 
            int left = maxDepth(node.left); 
            int right = maxDepth(node.right); 
   
            if(left > right) 
                return (left + 1); 
             else 
                return (right + 1); 
        } 
    } 
       
    public static void main(String[] args){ 
        BinaryTree tree = new BinaryTree(); 
   
        tree.root = new Node(2); 
        tree.root.left = new Node(3); 
        tree.root.right = new Node(8); 
        tree.root.left.left = new Node(6); 
        tree.root.left.right = new Node(9); 
   
        System.out.println(tree.maxDepth(tree.root)); 
    } 
}
3

پيچيدگي تجزيي

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

اي (اين) جتي نمبر ڏنل بائنري وڻ ۾ داخل ٿيل ڊيٽا نوڊس جو تعداد.

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

اي (1) ڇاڪاڻ ته اسان مسلسل اضافي جڳهه استعمال ڪيو.

حوالا