आइए मान लें कि हमारे पास एक बाइनरी ट्री का रूट नोड है; कार्य प्रत्येक नोड के झुकाव के योग को खोजना और वापस करना है।
झुकाव एक बाइनरी ट्री कुछ भी नहीं है, बल्कि प्रत्येक स्तर में लेफ्ट सबट्री और राइट सबट्री में चाइल्ड नोड्स के पूर्ण अंतर को खोजकर बाइनरी ट्री का निर्माण करना है। किसी विशेष स्तर पर, जिन नोड्स में कोई चाइल्ड नोड नहीं होता है, हम केवल उस नोड को शून्य से बदलकर झुकाते हैं।
उदाहरण
इनपुट
<मजबूत> 
आउटपुट:15
स्पष्टीकरण: दिए गए बाइनरी ट्री के हर स्तर पर झुकाव का पता लगाना,
नोड 3 का झुकाव =0
नोड का झुकाव 5 =0
नोड 7 का झुकाव =0
नोड 2 का झुकाव =abs(3-5)=2
नोड का झुकाव 9 =abs(0-7)=7
नोड का झुकाव 4 =abs((3+5+2)- (9+7))=6
सभी नोड्स के झुकाव का योग =2+7+6=15
इस समस्या को हल करने का तरीका
इस विशेष समस्या को हल करने का सरल तरीका पोस्ट ऑर्डर चौड़ाई प्रथम खोज ट्रैवर्सल का उपयोग करना है।
बाइनरी ट्री को पार करते समय, हम इसके लेफ्ट सबट्री और फिर राइट सबट्री के सभी नोड्स का योग खोजने की कोशिश करेंगे। एक बार योग मिल जाने के बाद, हम इसके बाएँ योग और उप-वृक्षों के दाएँ योग के निरपेक्ष अंतर की गणना करके सभी नोड्स के झुकाव का पता लगाएंगे।
- एक बाइनरी ट्री लें, जो इनपुट होगा।
- एक पूर्णांक फ़ंक्शन sumNodes(treenode*node) पेड़ के रूट नोड को लेता है और बाएं सबट्री और राइट सबट्री का योग देता है।
- एक पूर्णांक फ़ंक्शन findTilt(treenode*root) रूट नोड को इनपुट पैरामीटर के रूप में लेता है और सभी नोड्स के झुकाव का योग देता है।
उदाहरण
#include<iostream>
using namespace std;
struct treenode {
int data;
treenode * left;
treenode * right;
};
struct treenode * createNode(int d) {
struct treenode * root = new treenode;
root -> data = d;
root -> left = NULL;
root -> right = NULL;
return root;
}
int sumNodes(treenode * root, int & sum) {
if (root == NULL) return 0;
int lsum = sumNodes(root -> left, sum);
int rsum = sumNodes(root -> right, sum);
sum += abs(lsum - rsum);
return lsum + rsum + root -> data;
}
int findTilt(treenode * root) {
int sum = 0;
if (root == NULL) {
return 0;
}
sumNodes(root, sum);
return sum;
}
int main() {
struct treenode * root = NULL;
root = createNode(4);
root -> left = createNode(2);
root -> right = createNode(9);
root -> left -> right = createNode(5);
root -> left -> left = createNode(3);
root -> right -> right = createNode(7);
cout << findTilt(root) << endl;
return 0;
} उपरोक्त कोड को चलाने से आउटपुट इस प्रकार उत्पन्न होगा,
आउटपुट
15
दिए गए बाइनरी ट्री में, पेड़ के हर स्तर पर सभी नोड्स के झुकाव का योग 15 है।