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.
Share your method, a shortcut, or ask about a step you didn't follow.
No comments yet. Be the first to share your solution!
We use Google Analytics cookies to see how LearnFrenzy is used and make it better, and Google AdSense to keep it free.
No analytics or ad cookies are set until you accept. Privacy Policy
·
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!