import java.io.*;
import java.util.*;
// Java program to construct BST from given preorder traversal
class Node {
int data;
Node left, right;
Node(int d) {
data = d;
left = right = null;
}
}
class BinaryTree {
Node constructTree(int arr[], int start, int end) {
Node root=null,head=null;
if(end>0) {
root=new Node(arr[start++]);
head=root;
} else return null;
for(int i=start;i<=end;) {
root=head;
while(true) {
if(root.data>=arr[i] && root.left!=null) {
root=root.left;
} else if(root.data>=arr[i] && root.left==null){
root.left=new Node(arr[i++]);
break;
}
if(root.data<=arr[i] && root.right!=null) {
root=root.right;
} else if(root.data<=arr[i] && root.right==null){
root.right=new Node(arr[i++]);
break;
}
}
}
return head;
}
void printInorder(Node node) {
if (node == null) {
return;
}
printInorder(node.left);
System.out.print(node.data + " ");
printInorder(node.right);
}
public static void main(String[] args) {
BinaryTree tree = new BinaryTree();
int pre[] = new int[]{10, 5, 1, 7, 40, 50};
System.out.println("Inorder traversal of the constructed tree is ");
Node root = tree.constructTree(pre,0,pre.length-1);
tree.printInorder(root);
}
}
Saturday, 1 September 2018
Java program to construct BST from given preorder traversal.
Subscribe to:
Post Comments (Atom)
No comments:
Post a Comment