Topic: Tree
1) Level order traversal in Spiral form | Easy |
2) Zig Zag Traversal | Easy |
3) Maximum Width of Binary Tree | Easy |
4) Left view of Binary Tree | Easy |
5) Right view of Binary Tree | Easy |
Level order traversal in Spiral form
Input:
10
/ \
20 30
/ \
40 60
Output: 10 20 30 60 40
int level = 1;
ArrayList<Integer> findSpiral(Node root)
{
ArrayList<Integer> final_arr = new ArrayList<>();
// <------ edge case ----->
if(root==null){
return final_arr;
}
Stack<Node> main_stack = new Stack<>();
Stack<Node> child_stack = new Stack<>();
// <------ for root node ----->
main_stack.push(root);
// imp line
while((!main_stack.isEmpty())||(!child_stack.isEmpty())){
// <------ for odd level ----->
if(level%2==1){
// main stack is used to pop out
while(!main_stack.isEmpty()){
Node node1 = main_stack.pop();
// add popped out element to arraylist
final_arr.add(node1.data);
// children push direction L to R in child stack
// only below two lines are interchanged if compared to zig zag traversal
if(node1.right!=null){child_stack.push(node1.right);}
if(node1.left!=null){child_stack.push(node1.left);}
}
level++;
}
// <------ for even level ----->
if(level%2==0){
// child stack is used to pop out
while(!child_stack.isEmpty()){
Node node2 = child_stack.pop();
// add popped out element to arraylist
final_arr.add(node2.data);
// children push direction R to L in main stack
// only below two lines are interchanged if compared to zig zag traversal
if(node2.left!=null){main_stack.push(node2.left);}
if(node2.right!=null){main_stack.push(node2.right);}
}
level++;
}
}
return final_arr;
}
Zig Zag Traversal
Input:
7
/ \
9 7
/ \ /
8 8 6
/ \
10 9
Output:
7 7 9 8 8 6 9 10
int level = 1;
ArrayList<Integer> zigZagTraversal(Node root)
{
ArrayList<Integer> final_arr = new ArrayList<>();
// <------ edge case ----->
if(root==null){
return final_arr;
}
Stack<Node> main_stack = new Stack<>();
Stack<Node> child_stack = new Stack<>();
// <------ for root node ----->
main_stack.push(root);
while((!main_stack.isEmpty())||(!child_stack.isEmpty())){
// <------ for odd level ----->
if(level%2==1){
// main stack is used to pop out
while(!main_stack.isEmpty()){
Node node1 = main_stack.pop();
// add popped out element to arraylist
final_arr.add(node1.data);
// children push direction L to R in child stack
if(node1.left!=null){child_stack.push(node1.left);}
if(node1.right!=null){child_stack.push(node1.right);}
}
level++;
}
// <------ for even level ----->
if(level%2==0){
// child stack is used to pop out
while(!child_stack.isEmpty()){
Node node2 = child_stack.pop();
// add popped out element to arraylist
final_arr.add(node2.data);
// children push direction R to L in main stack
if(node2.right!=null){main_stack.push(node2.right);}
if(node2.left!=null){main_stack.push(node2.left);}
}
level++;
}
}
return final_arr;
}
Maximum Width of Binary Tree
Input:
10
/ \
20 30
/ \
40 60
Output: 2
There is one node on level 1(10)
There is two node on level 2(20, 30)
There is two node on level 3(40, 60)
Hence the answer is 2
import java.util.ArrayList;
import java.util.Collections;
import java.util.LinkedList;
import java.util.Queue;
public class maximumwidthofTree {
int getMaxWidth(Node root) {
ArrayList<Integer> main_arr = new ArrayList<>();
ArrayList<Integer> child_arr = new ArrayList<>();
if(root==null){
return 0;
}
Queue<Node> main_queue = new LinkedList<>();
main_queue.add(root);
main_queue.add(null);
main_arr.add(1);
while(main_queue.size()>1){
root = main_queue.poll();
if(root==null){
main_queue.add(null);
// only below line is changed from left view and right view
main_arr.add(child_arr.size());
child_arr = new ArrayList<>();
continue;
}
if(root.left!=null){
main_queue.add(root.left);
child_arr.add(root.left.data);
}
if(root.right!=null){
main_queue.add(root.right);
child_arr.add(root.right.data);
}
}
Integer result = Collections.max(main_arr);
int i = result.intValue();
return i;
}
}
Left view of Binary Tree
1
/ \
2 3
/ \ / \
4 5 6 7
\
8
O/P -> 1 2 4 8
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
public class leftviewofBinaryTree {
ArrayList<Integer> leftView(Node root)
{
ArrayList<Integer> main_arr = new ArrayList<>();
ArrayList<Integer> child_arr = new ArrayList<>();
if(root==null){
return main_arr;
}
Queue<Node> main_queue = new LinkedList<>();
main_queue.add(root);
main_queue.add(null);
main_arr.add(root.data);
while(main_queue.size()>1){
root = main_queue.poll();
if(root==null){
main_queue.add(null);
main_arr.add(child_arr.get(0));
child_arr = new ArrayList<>();
continue;
}
if(root.left!=null){
main_queue.add(root.left);
child_arr.add(root.left.data);
}
if(root.right!=null){
main_queue.add(root.right);
child_arr.add(root.right.data);
}
}
return main_arr;
}
}
Right view of Binary Tree
1
/ \
2 3
/ \ / \
4 5 6 7
\
8
O/p -> 1 3 7 8
Input:
10
/ \
20 30
/ \
40 60
Output: 10 30 60
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
public class rightviewofBinaryTree {
ArrayList<Integer> rightView(Node root) {
ArrayList<Integer> main_arr = new ArrayList<>();
ArrayList<Integer> child_arr = new ArrayList<>();
if(root==null){
return main_arr;
}
Queue<Node> main_queue = new LinkedList<>();
main_queue.add(root);
main_queue.add(null);
main_arr.add(root.data);
while(main_queue.size()>1){
root = main_queue.poll();
if(root==null){
main_queue.add(null);
// only below line is changed from left view
main_arr.add(child_arr.get(child_arr.size()-1));
child_arr = new ArrayList<>();
continue;
}
if(root.left!=null){
main_queue.add(root.left);
child_arr.add(root.left.data);
}
if(root.right!=null){
main_queue.add(root.right);
child_arr.add(root.right.data);
}
}
return main_arr;
}
}
Thank you for reading :)