यहां हम देखेंगे कि कैसे जांचा जाए कि बाइनरी ट्री सम-ट्री है या नहीं। अब प्रश्न यह है कि योग वृक्ष क्या है। सम-ट्री एक बाइनरी ट्री है जहाँ एक नोड अपने बच्चों का योग मान रखेगा। पेड़ की जड़ में उसके नीचे के सभी तत्वों का योग होगा। यह सम-वृक्ष का उदाहरण है -
इसे चेक करने के लिए हम एक आसान सी ट्रिक अपनाएंगे, हम लेफ्ट और राइट सबट्री एलिमेंट्स का योग पाएंगे अगर योग वैल्यू रूट के समान है, तो वह सम-ट्री है। यह एक पुनरावर्ती दृष्टिकोण होगा।
उदाहरण
#include <bits/stdc++.h>
using namespace std;
class node {
public:
int data;
node* left, *right;
};
int sum_of_nodes(node *root) {
if(root == NULL)
return 0;
return sum_of_nodes(root->left) + root->data + sum_of_nodes(root->right);
}
int isSumTree(node* node) {
int left_sum, right_sum;
if(node == NULL || (node->left == NULL && node->right == NULL))
return 1;
left_sum = sum_of_nodes(node->left);
right_sum = sum_of_nodes(node->right);
if((node->data == left_sum + right_sum) && isSumTree(node->left) && isSumTree(node->right))
return 1;
return 0;
}
node* getNode(int data) {
node* newNode = new node();
newNode->data = data;
newNode->left = newNode->right = NULL;
return newNode;
}
int main() {
node *root = getNode(26);
root->left = getNode(10);
root->right = getNode(3);
root->left->left = getNode(4);
root->left->right = getNode(6);
root->right->right = getNode(3);
if(isSumTree(root))
cout << "The tree is Sum Tree";
else
cout << "The tree is not a Sum Tree";
} आउटपुट
The tree is Sum Tree