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

এই সমস্যায়, আমাদের একটি বাইনারি ট্রি দেওয়া আছে। আমাদের কাজ হল বাইনারি ট্রিতে সকল বাম পাতা নোডের যোগফল বের করা।

উদাহরণ

সমস্যাটি বুঝতে একটি উদাহরণ নিই:

ইনপুট :

আউটপুট : 11

ব্যাখ্যা:

ট্রির সব পাতা নোড: 2, 9
যোগফল = 2 + 9 = 11

সমাধানের পদ্ধতি

এই সমস্যার একটি সহজ সমাধান হল ট্রি রুট থেকে পাতা পর্যন্ত ট্রাভার্স করা। যদি কোনো নোড বাম পাতা নোড হয়, তবে তা যোগফলে যোগ করুন। পুরো ট্রি ট্রাভার্স হলে যোগফল প্রিন্ট করুন।

পদ্ধতি ১: রিকার্সিভ পদ্ধতি

প্রোগ্রাম যা আমাদের সমাধান ব্যাখ্যা করবে:

#include <iostream>
using namespace std;

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

Node* newNode(char k) {
    Node* node = new Node;
    node->key = k;
    node->right = node->left = NULL;
    return node;
}

bool isLeafNode(Node* node) {
    if (node == NULL)
        return false;
    if (node->left == NULL && node->right == NULL)
        return true;
    return false;
}

int findLeftLeavesSum(Node* root) {
    int sum = 0;
    if (root != NULL) {
        if (isLeafNode(root->left))
            sum += root->left->key;
        else
            sum += findLeftLeavesSum(root->left);
        sum += findLeftLeavesSum(root->right);
    }
    return sum;
}

int main() {
    struct Node* root = newNode(5);
    root->left = newNode(4);
    root->right = newNode(6);
    root->left->left = newNode(2);
    root->left->right = newNode(1);
    root->right->left = newNode(9);
    root->right->right = newNode(7);
    cout << "The sum of left leaves of the tree is " << findLeftLeavesSum(root);
    return 0;
}

আউটপুট

The sum of left leaves of the tree is 11

পদ্ধতি ২: ইটারেটিভ পদ্ধতি (DFS স্ট্যাক ব্যবহার করে)

আমরা ট্রিতে ডেপথ ফার্স্ট সার্চ ট্রাভার্সাল করব, এবং তারপর যাচাই করব বর্তমান নোড বাম পাতা নোড কি না। যদি হয়, তবে এর মান যোগফলে যোগ করব, অন্যথায় ছেড়ে দিব। শেষে যোগফল প্রিন্ট করব।

উদাহরণ প্রোগ্রাম

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

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

Node* newNode(char k) {
    Node* node = new Node;
    node->key = k;
    node->right = node->left = NULL;
    return node;
}

int findLeftLeavesSum(Node* root) {
    if (root == NULL)
        return 0;
    stack<Node*> treeNodes;
    treeNodes.push(root);
    int sum = 0;
    while (treeNodes.size() > 0) {
        Node* currentNode = treeNodes.top();
        treeNodes.pop();
        if (currentNode->left != NULL) {
            treeNodes.push(currentNode->left);
            if (currentNode->left->left == NULL &&
                currentNode->left->right == NULL) {
                sum += currentNode->left->key;
            }
        }
        if (currentNode->right != NULL)
            treeNodes.push(currentNode->right);
    }
    return sum;
}

int main() {
    Node* root = newNode(5);
    root->left = newNode(4);
    root->right = newNode(6);
    root->left->left = newNode(2);
    root->left->right = newNode(1);
    root->right->left = newNode(9);
    root->right->right = newNode(7);
    cout << "The sum of left leaves of the tree is " << findLeftLeavesSum(root);
    return 0;
}

আউটপুট

The sum of left leaves of the tree is 11

পদ্ধতি ৩: BFS ব্যবহার করে

আমরা ব্রেডথ ফার্স্ট সার্চ করব একটি ভেরিয়েবল দিয়ে যা নির্দেশ করবে নোডটি বাম চাইল্ড কি না। যদি হয়, তবে যোগফলে যোগ করব, অন্যথায় ছেড়ে দিব। শেষে যোগফল প্রিন্ট করব।

উদাহরণ প্রোগ্রাম

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

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

Node* newNode(char k) {
    Node* node = new Node;
    node->key = k;
    node->right = node->left = NULL;
    return node;
}

int findLeftLeavesSum(Node* root) {
    if (root == NULL)
        return 0;
    queue<pair<Node*, bool> > leftTreeNodes;
    leftTreeNodes.push({ root, 0 });
    int sum = 0;
    while (!leftTreeNodes.empty()) {
        Node* temp = leftTreeNodes.front().first;
        bool is_left_child = leftTreeNodes.front().second;
        leftTreeNodes.pop();
        if (!temp->left && !temp->right && is_left_child)
            sum = sum + temp->key;
        if (temp->left) {
            leftTreeNodes.push({ temp->left, 1 });
        }
        if (temp->right) {
            leftTreeNodes.push({ temp->right, 0 });
        }
    }
    return sum;
}

int main() {
    Node* root = newNode(5);
    root->left = newNode(4);
    root->right = newNode(6);
    root->left->left = newNode(2);
    root->left->right = newNode(1);
    root->right->left = newNode(9);
    root->right->right = newNode(7);
    cout << "The sum of left leaves of the tree is " << findLeftLeavesSum(root);
    return 0;
}

আউটপুট

The sum of left leaves of the tree is 11