LearnFrenzy
Sign in Take a free test

Data Structures in Java · Data Structures in Java Programs · Question 6

Left view, right view and level sums of a tree Solution, output & explanation

  • Program
  • Medium
  • 0 comments
  • Answer explained
  • Moderated community
Question 6 Back to Exercise

Using one level-order traversal, print the left view (first node of each level), the right view (last node of each level) and the sum of each level of a binary tree.

Solution
Main.java
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.List;

public class Main {
    static class Node {
        int key;
        Node left, right;
        Node(int key) { this.key = key; }
    }

    static Node insert(Node n, int k) {
        if (n == null) return new Node(k);
        if (k < n.key) n.left = insert(n.left, k);
        else n.right = insert(n.right, k);
        return n;
    }

    public static void main(String[] args) {
        Node root = null;
        for (int k : new int[]{8, 4, 12, 2, 6, 10, 14, 1, 7}) root = insert(root, k);

        List<Integer> left = new ArrayList<>(), right = new ArrayList<>(), sums = new ArrayList<>();
        Deque<Node> q = new ArrayDeque<>();
        q.add(root);
        while (!q.isEmpty()) {
            int n = q.size(), sum = 0;                 // everything in the queue now is one level
            for (int i = 0; i < n; i++) {
                Node cur = q.poll();
                if (i == 0) left.add(cur.key);
                if (i == n - 1) right.add(cur.key);
                sum += cur.key;
                if (cur.left != null) q.add(cur.left);
                if (cur.right != null) q.add(cur.right);
            }
            sums.add(sum);
        }
        System.out.println("left view:  " + left);
        System.out.println("right view: " + right);
        System.out.println("level sums: " + sums);
    }
}

Output Verified by compiling and running

left view:  [8, 4, 2, 1]
right view: [8, 12, 14, 7]
level sums: [8, 16, 32, 8]

The last level holds 1 (under 2) and 7 (under 6), so 7 is visible from the right even though it is in the left subtree.

Discussion & Comments 0

Share your method, a shortcut, or ask about a step you didn't follow.

No comments yet. Be the first to share your solution!

Post your comment

Comments appear after a quick review by our team.

Search LearnFrenzy

Esc

Quick links