C++-এ বাইনারি ট্রি হাইট-ব্যালেন্সড কিনা যাচাই করার প্রোগ্রাম

সমস্যা বিবরণ

একটি বাইনারি ট্রি দেওয়া থাকলে, যাচাই করতে হবে কি এটি হাইট-ব্যালেন্সড (Height Balanced)। একটি ট্রি হাইট-ব্যালেন্সড হয় যদি প্রতিটি নোডের জন্য এর লেফ্ট ও রাইট সাবট্রির হাইটের পার্থক্য ০ বা ১ হয়।

উদাহরণ: রুট=২৫, লেফ্ট=১৯, রাইট=৪, ১৯-এর চাইল্ডরা ৯ ও ৭ → এটি ব্যালেন্সড, আউটপুট True (1)।

সমাধানের পদ্ধতি (Post-order DFS)

1. একটি গ্লোবাল ভেরিয়েবল ret = true রাখুন।
2. DFS ফাংশন লিখুন যা নোড নেবে এবং সাবট্রির হাইট রিটার্ন করবে।
3. বেস কেস: নোড NULL হলে 0 রিটার্ন।
4. লেফ্ট হাইট l = 1 + dfs(node->left)
5. রাইট হাইট r = 1 + dfs(node->right)
6. যদি abs(l - r) > 1 হয়, তবে ret = false।
7. max(l, r) রিটার্ন করুন।
8. মেইন থেকে dfs(root) কল করুন এবং ret রিটার্ন করুন।

C++ কোড উদাহরণ

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

class TreeNode {
public:
    int val;
    TreeNode *left, *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

class Solution {
public:
    bool ret;
    int dfs(TreeNode* node) {
        if (!node) return 0;
        int l = 1 + dfs(node->left);
        int r = 1 + dfs(node->right);
        if (abs(l - r) > 1) ret = false;
        return max(l, r);
    }
    bool isBalanced(TreeNode* root) {
        ret = true;
        dfs(root);
        return ret;
    }
};

int main() {
    Solution ob;
    TreeNode *root = new TreeNode(25);
    root->left = new TreeNode(19);
    root->right = new TreeNode(4);
    root->left->left = new TreeNode(9);
    root->left->right = new TreeNode(7);
    cout << (ob.isBalanced(root));
    return 0;
}

ইনপুট ও আউটপুট

ইনপুট: বর্ণিত ট্রি

আউটপুট: 1 (True)

জটিলতা

• সময়: O(n) — প্রতিটি নোড একবার ভিজিট
• স্থান: O(h) — রিকার্সন স্ট্যাক, h = ট্রির হাইট