We have implemented left view and right view of BST using recursion.
============Tree Structure like below============
20
/ \
10 30
\ / \
15 25 35
\
26
\
27
Left View :- 20 10 15 26 27
Right View :- 20 30 35 26 27
=================================================
package com.java.recursion;
import java.util.Scanner;
public class LeftViewOfBST {
public static Node root;
public static int count = 0;
public static int maxValue=0;
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
while (true) {
System.out.println("1. Create \t2. InOrder \t3. leftviewOfBST \t4. rightViewOfTree");
int operation = sc.nextInt();
switch (operation) {
case 1:
System.out.println("How many node you want to create");
int noOfNode = sc.nextInt();
for (int i = 0; i < noOfNode; i++) {
System.out.println("Enter node value");
int data = sc.nextInt();
create(data);
}
break;
case 2:
InOrder(root);
System.out.println();
break;
case 3:
leftviewOfBST(root);
System.out.println();
break;
case 4:
rightViewOfTree(root,0);
System.out.println();
break;
}
}
}
private static void create(int data) {
Node temp = new Node(data);
if (root == null) {
root = temp;
return;
}
Node copy = root;
Node CR = root;
while (copy != null) {
CR = copy;
if (copy.data > data) {
copy = copy.left;
} else if (copy.data < data) {
copy = copy.right;
}
}
if (CR.data > data) {
CR.left = temp;
} else if (CR.data < data) {
CR.right = temp;
}
}
private static void InOrder(Node root) {
if (root == null) {
return;
}
InOrder(root.left);
System.out.print(root.data + " ");
InOrder(root.right);
}
private static void leftviewOfBST(Node root) {
if (root == null) {
return;
}
int height = height(root);
for (int i = 1; i <= height; i++) {
count = 0;
printLeftView(root, i);
}
}
private static void printLeftView(Node root, int level) {
if (root == null) {
return;
}
if (level == 1 && count == 0) {
System.out.println(root.data + " ");
count++;
return;
}
printLeftView(root.left, level - 1);
printLeftView(root.right, level - 1);
}
private static int height(Node root) {
if (root == null) {
return 0;
}
return max(height(root.left), height(root.right)) + 1;
}
private static int max(int a, int b) {
return a > b ? a : b;
}
private static void rightViewOfTree(Node root,int level) {
if(root==null){
return;
}
if(level>=maxValue){
System.out.print(root.data+" ");
maxValue++;
}
rightViewOfTree(root.right,level+1);
rightViewOfTree(root.left,level+1);
}
}
========== Output of the program ============
1. Create 2. InOrder 3. leftviewOfBST 4. rightViewOfTree
1
How many node you want to create
8
Enter node value
20
Enter node value
10
Enter node value
30
Enter node value
15
Enter node value
25
Enter node value
35
Enter node value
26
Enter node value
27
1. Create 2. InOrder 3. leftviewOfBST 4. rightViewOfTree
2
10 15 20 25 26 27 30 35
1. Create 2. InOrder 3. leftviewOfBST 4. rightViewOfTree
3
20
10
15
26
27
1. Create 2. InOrder 3. leftviewOfBST 4. rightViewOfTree
4
20 30 35 26 27
1. Create 2. InOrder 3. leftviewOfBST 4. rightViewOfTree
No comments:
Post a Comment