जावा में बाइनरी ट्री के विषम और सम लेवल नोड्स के योग का अंतर

समस्या कथन

एक दिए गए बाइनरी ट्री के साथ, विषम लेवल पर नोड्स के योग और सम लेवल पर नोड्स के योग के बीच अंतर ज्ञात करने के लिए एक प्रोग्राम लिखें। रूट को लेवल 1 मानें, रूट के बाएं/दाएं चाइल्ड को लेवल 2 और इसी तरह आगे।

उदाहरण

        5 
       / \ 
      2   6 
     / \   \ 
    1   4   8 
   /   / \ 
  3   7   9 

विषम लेवल पर नोड्स का योग = 5 + 1 + 4 + 8 = 18
सम लेवल पर नोड्स का योग = 2 + 6 + 3 + 7 + 9 = 27
अंतर = -9

समाधान

रिकर्सिव ट्रैवर्सल का उपयोग करें। ट्रैवर्सल के दौरान, रूट नोड और उसके बाएं और दाएं चाइल्ड के अंतर को वापस करें।

उदाहरण

आवश्यक आउटपुट खोजने के लिए जावा में निम्न प्रोग्राम है।

class Node { 
    int data; 
    Node left, right; 
    Node(int data){ 
        this.data = data; 
        this.left = this.right = null; 
    } 
} 

public class JavaTester { 
    public static Node getTree(){ 
        Node root = new Node(5); 
        root.left = new Node(2); 
        root.right = new Node(6); 
        root.left.left = new Node(1); 
        root.left.right = new Node(4); 
        root.left.right.left = new Node(3); 
        root.right.right = new Node(8); 
        root.right.right.right = new Node(9); 
        root.right.right.left = new Node(7); 
        return root; 
    } 
    
    public static int difference(Node node){ 
        if(node == null) return 0; 
        return node.data - difference(node.left) - difference(node.right); 
    } 
    
    public static void main(String args[]){ 
        Node tree = getTree(); 
        System.out.println(difference(tree)); 
    } 
}

आउटपुट

-9