বাইনারি ট্রিয়ে সবচেয়ে গভীর নোড বের করা (C++)

সমস্যা বিবরণ

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

উদাহরণ

ট্রি (চিত্র) → আউটপুট: ৮

পদ্ধতি ১: ইন-অর্ডার ট্রাভার্সাল + লেভেল ট্র্যাক (O(n))

রিকার্সিভ ইন-অর্ডার ট্রাভার্সালে করেন্ট লেভেল ম্যাক্স লেভেল চেক করে deepestNode আপডেট করা।

পদ্ধতি ২: হাইট বের করে সে লেভেলের নোড প্রিন্ট (O(n))

প্রথমে ট্রির হাইট বের করা, তারপর সেই লেভেলের নোড প্রিন্ট করা।

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

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

int height(Node* r){ return r? 1+max(height(r->left),height(r->right)) : 0; }

void deepest(Node* r, int lvl){
    if(!r) return;
    if(lvl==1) cout<<r->data;
    else{ deepest(r->left,lvl-1); deepest(r->right,lvl-1); }
}

int main(){
    Node* root = new Node{3};
    root->left=new Node{5}; root->right=new Node{4};
    root->left->left=new Node{1}; root->left->right=new Node{9};
    root->right->left=new Node{6}; root->right->left->right=new Node{8};
    deepest(root, height(root)); // 8
    return 0;
}