-
Notifications
You must be signed in to change notification settings - Fork 17
/
ConstructBST.java
50 lines (38 loc) · 1.02 KB
/
ConstructBST.java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
package bst;
import java.util.Scanner;
public class ConstructBST {
public static void main(String[] args) {
Scanner sc = new Scanner (System.in);
System.out.println("Enter no of elements in preorder :");
int n = sc.nextInt();
System.out.println("Enter Elements of Preorder :");
int preorder[] = new int [n];
for(int i=0; i<n ; i++) {
preorder[i] = sc.nextInt();
}
Node root = constructTree(preorder, 0, n-1);
System.out.println("Inorder traversal of BST is :");
inorder(root);
sc.close();
}
static Node constructTree(int preorder[], int start, int end) {
if(start > end) {
return null;
}
Node root = new Node (preorder[start]);
int i;
for(i=start; i<=end ; i++) {
if(preorder[i] > root.data)
break;
}
root.left = constructTree(preorder, start+1, i-1);
root.right = constructTree(preorder, i, end);
return root;
}
static void inorder(Node root) {
if(root == null) return;
inorder(root.left);
System.out.print(root.data + " ");
inorder(root.right);
}
}