সি++-এ বাইনারি ট্রির গভীরতম বিজোড় লেভেল নোডের গভীরতা

প্রথমে স্ট্রাক্ট ডিফাইন করি যা ট্রি নোড রিপ্রেজেন্ট করবে যাতে int key এবং এর বাম ও ডান চাইল্ড নোড থাকে। যদি এটি প্রথম নোড হয় তবে এটি রুট নোড হবে অন্যথায় চাইল্ড নোড।

struct Node { 
    int data; 
    struct Node *leftChild, *rightChild; 
};

পরবর্তীতে createNode(int key) ফাংশন তৈরি করি যা একটি int key মান নেয় এবং সেটি নোডের key মেম্বরে অ্যাসাইন করে। ফাংশনটি তৈরি হওয়া struct Node-এর পয়েন্টার ফেরত দেয়। এছাড়া নতুন নোডের বাম ও ডান চাইল্ড নাল সেট করা হয়।

Node* createNode(int data){ 
    Node* node = new Node; 
    node->data = data; 
    node->leftChild = node->rightChild = NULL; 
    return node; 
}

পরবর্তীতে isLeaf(Node *currentNode) ফাংশন আছে যা একটি নোড নেয় এবং চেক করে এর কি চাইল্ড আছে কিনা। এটি true বা false ফেরত দেয় নোডটি ليف নোড কিনা সেটা ভিত্তি করে।

bool isLeaf(Node *currentNode){ 
    return (currentNode->leftChild == NULL && 
    currentNode->rightChild == NULL); 
}

deepestOddLvlDepth(Node *currentNode, int currentLevel=0) করেন্ট নোড এবং করেন্ট লেভেল নেয়। currentLevel-এর ডিফল্ট মান ০ যদি কোনো মান পাস না করা হয়। যদি currentNode NULL হয় তবে ফাংশন ০ ফেরত দেয়।

int deepestOddLvlDepth(Node *currentNode, int currentLevel=0){ 
    if ( currentNode == NULL) 
        return 0;

currentLevel প্রতিটি রিকার্শন লেভেলে ১ করে বাড়ায় যতক্ষণ বেস কন্ডিশন মিট হয়। তারপর চেক করি currentNode বিজোড় ليف নোড কিনা। বাম ও ডান চাইল্ড ট্রাভার্স করা হয় যতক্ষণ আমাদের গভীরতম বিজোড় লেভেল ليف নোডের ডেপথ পাওয়া যায়। বাম ও ডান চাইল্ড ডেপথের ম্যাক্সিমাম মেইন ফাংশনে ফেরত দেওয়া হয় রেজাল্ট প্রিন্ট করার জন্য।

int deepestOddLvlDepth(Node *currentNode, int currentLevel=0){ 
    if ( currentNode == NULL) 
        return 0; 
    currentLevel ++; 
    if ( currentLevel % 2 != 0 && isLeaf(currentNode)) 
        return currentLevel; 
    int leftChildLevel = deepestOddLvlDepth(currentNode->leftChild,currentLevel); 
    int rightChildLevel = deepestOddLvlDepth(currentNode->rightChild,currentLevel); 
    return max(leftChildLevel,rightChildLevel); 
}

উদাহরণ

বাইনারি ট্রিতে গভীরতম বিজোড় লেভেল নোডের ডেপথ বের করার ইমপ্লিমেন্টেশন:

#include<iostream> 
using namespace std; 

struct Node{ 
    int key; 
    struct Node *leftChild, *rightChild; 
}; 

Node* createNode(int key){ 
    Node* node = new Node; 
    node->key = key; 
    node->leftChild = node->rightChild = NULL; 
    return node; 
} 

bool isLeaf(Node *currentNode){ 
    return (currentNode->leftChild == NULL && 
    currentNode->rightChild == NULL); 
} 

int deepestOddLvlDepth(Node *currentNode, int currentLevel=0){ 
    if ( currentNode == NULL) 
        return 0; 
    currentLevel ++; 
    if ( currentLevel % 2 != 0 && isLeaf(currentNode)) 
        return currentLevel; 
    int leftChildLevel = deepestOddLvlDepth(currentNode->leftChild,currentLevel); 
    int rightChildLevel = deepestOddLvlDepth(currentNode->rightChild,currentLevel); 
    return max(leftChildLevel,rightChildLevel); 
} 

int main(){ 
    Node *root = createNode(15); 
    root->leftChild = createNode(33); 
    root->rightChild = createNode(18); 
    root->rightChild->leftChild = createNode(19); 
    root->rightChild->rightChild = createNode(20); 
    root->rightChild->rightChild->leftChild = createNode(28); 
    root->rightChild->rightChild->rightChild = createNode(29); 
    cout << "The depth of the deepest odd level leaf node is: "<<deepestOddLvlDepth(root) << endl; 
    return 0; 
}

আউটপুট

The depth of the deepest odd level leaf node is: 3