জাভাতে বাইনারি ট্রির অড পজিশন এবং ইভেন পজিশন নোডগুলোর যোগফলের পার্থক্য

সমস্যা বিবরণ

একটি বাইনারি ট্রি দেওয়া আছে। রুট লেভেল ০ (অড পজিশন), রুটের লেফট/রাইট চাইল্ড লেভেল ২ (লেফট চাইল্ড অড পজিশন, রাইট চাইল্ড ইভেন পজিশন) এবং এভাবেই ক্রমাগত। অড পজিশন এবং ইভেন পজিশনে থাকা নোডগুলোর যোগফলের পার্থক্য বের করতে হবে।

উদাহরণ

      5 
     / \ 
    2   6 
   / \   \ 
  1   4   8 
 /       / \ 
3       7   9 
Sum of nodes at odd positions = 5 + 2 + (1 + 8) + (3 + 9) = 28 
Sum of nodes at even positions = 0 + 6 + 4 + 7 = 17 
Difference = 11

সমাধান

Level Order Traversal ব্যবহার করা হয়েছে। ট্র্যাভার্সালের সময় প্রথম এলিমেন্টকে অড পজিশন হিসেবে চিহ্নিত করে তারপর নতুন এলিমেন্ট পাওয়ার সাথে সাথে ইভেন-অড পজিশন অল্টারনেট করা হয়।

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

import java.util.LinkedList; 
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(LinkedList<Node> queue){ 
        if(queue.isEmpty()) return 0; 
        int evenSum = 0; 
        int oddSum = 0; 
        while(true){ 
            int nodes = queue.size(); 
            if(nodes == 0) break; 
            boolean isOdd = true; 
            while(nodes > 0){ 
                Node node = queue.peek(); 
                if(isOdd) oddSum += node.data; 
                else evenSum += node.data; 
                queue.remove(); 
                nodes--; 
                if(node.left != null) queue.add(node.left); 
                if(node.right != null) queue.add(node.right); 
                isOdd = !isOdd; 
            } 
        } 
        return oddSum - evenSum; 
    } 
    public static void main(String args[]){ 
        Node tree = getTree(); 
        LinkedList<Node> queue = new LinkedList<Node>(); 
        queue.add(tree); 
        System.out.println(difference(queue)); 
    } 
}

আউটপুট

11