C++-এ বাইনারি ট্রির গভীরতম নোড খুঁজুন

একটি বাইনারি ট্রি দেওয়া আছে। আমাদের কাজ হচ্ছে সর্বাধিক গভীরতম নোড (Deepest Node) বের করা।

বাইনারি ট্রি হল একটি ডেটা স্ট্রাকচার যেখানে প্রতিটি নোডে সর্বোচ্চ দুটি চাইল্ড থাকতে পারে। গভীরতম নোড হল ট্রিতে যেটি সর্বোচ্চ হাইটে অবস্থিত।

উদাহরণ

ইনপুট ট্রি देखकर আউটপুট: 8

সমাধান ১: ইনঅর্ডার ট্রাভার্সাল + লেভেল ট্র্যাকিং

ইনঅর্ডার ট্রাভার্সাল চলাকালীন বর্তমান লেভেল ট্র্যাক রাখুন। যদি বর্তমান লেভেল maxLevel-এর চেয়ে বড় হয়, তবে deepestNode আপডেট করুন।

C++ প্রোগ্রাম

#include <iostream>
using namespace std;

struct Node {
    int data;
    struct Node *left, *right;
};

Node* newNode(int data) {
    Node* temp = new Node;
    temp->data = data;
    temp->left = temp->right = NULL;
    return temp;
}

void findDeepestNodeRec(Node* root, int currentLevel, int& maxLevel, int& deepestNode) {
    if (root != NULL) {
        findDeepestNodeRec(root->left, ++currentLevel, maxLevel, deepestNode);
        if (currentLevel > maxLevel) {
            deepestNode = root->data;
            maxLevel = currentLevel;
        }
        findDeepestNodeRec(root->right, currentLevel, maxLevel, deepestNode);
    }
}

int findDeepestNodeBT(Node* root) {
    int deepestNode = 0;
    int maxLevel = 0;
    findDeepestNodeRec(root, 0, maxLevel, deepestNode);
    return deepestNode;
}

int main() {
    Node* root = newNode(3);
    root->left = newNode(5);
    root->right = newNode(4);
    root->left->left = newNode(1);
    root->left->right = newNode(9);
    root->right->left = newNode(6);
    root->right->left->right = newNode(8);
    cout << "The deepest node of the given binary tree is " << findDeepestNodeBT(root);
    return 0;
}

আউটপুট

The deepest node of the given binary tree is 8

সমাধান ২: হাইট বের করে সেই লেভেলের নোড খুঁজুন

1. ট্রির হাইট বের করুন (calcHeight)।
2. রুট থেকে সেই লেভেল পর্যন্ত ট্রাভার্সাল করুন (findDeepestNodeBT)।

C++ প্রোগ্রাম

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

struct Node {
    int data;
    struct Node *left, *right;
};

Node* newNode(int data) {
    Node* temp = new Node;
    temp->data = data;
    temp->left = temp->right = NULL;
    return temp;
}

int calcHeight(Node* root) {
    if (!root) return 0;
    int leftHt = calcHeight(root->left) + 1;
    int rightHt = calcHeight(root->right) + 1;
    return max(leftHt, rightHt);
}

void findDeepestNodeBT(Node* root, int levels) {
    if (!root) return;
    if (levels == 1) cout << root->data;
    else if (levels > 1) {
        findDeepestNodeBT(root->left, levels - 1);
        findDeepestNodeBT(root->right, levels - 1);
    }
}

int main() {
    Node* root = newNode(3);
    root->left = newNode(5);
    root->right = newNode(4);
    root->left->left = newNode(1);
    root->left->right = newNode(9);
    root->right->left = newNode(6);
    root->right->left->right = newNode(8);
    int maxHeight = calcHeight(root);
    cout << "The deepest node of the binary tree is ";
    findDeepestNodeBT(root, maxHeight);
    return 0;
}

আউটপুট

The deepest node of the binary tree is 8

তুলনা

দুই পদ্ধতিই সময় ও স্পেস কমপ্লেক্সিটি একই। প্রথম পদ্ধতিতে একক ট্রাভার্সালে সমাধান হয়।