import java.util.ArrayDeque;
class SearchTree {
static boolean searchRecursive(Node root, int data) {
// base check
if(root == null) {
return false;
} else if(root.data == data) {
return true;
} else if(data < root.data) {
return searchRecursive(root.left, data);
} else {
return searchRecursive(root.right, data);
}
}
static boolean search(Node root, int data) {
if(root != null) {
while(root != null) {
if(root.data == data) {
return true;
}
root = data < root.data ? root.left : root.right;
}
}
return false;
}
static Node populateTree() {
Node root = new Node(4);
root.left = new Node(2);
root.right = new Node(6);
root.left.left = new Node(0);
root.left.right = new Node(3);
root.right.left = new Node(5);
root.right.right = new Node(7);
return root;
}
static void inOrderTraversal(Node root) {
if(root == null) {
return;
}
inOrderTraversal(root.left);
System.out.print(root.data + " ");
inOrderTraversal(root.right);
}
static void preOrderTraversal(Node root) {
if(root == null) {
return;
}
System.out.print(root.data + " ");
preOrderTraversal(root.left);
inOrderTraversal(root.right);
}
public static void main (String[] args) {
Node root = populateTree();
// traverse the constructed tree
System.out.print("The inorder traversal is ");
inOrderTraversal(root);
System.out.print("\nThe preorder traversal is ");
preOrderTraversal(root);
System.out.print("\nTree contains 3 : " + searchRecursive(root, 3));
System.out.print("\nTree contains 7 : " + searchRecursive(root, 7));
System.out.print("\nTree contains 80 : " + searchRecursive(root, 80));
System.out.print("\nTree contains 3 : " + search(root, 3));
System.out.print("\nTree contains 7 : " + search(root, 7));
System.out.print("\nTree contains 80 : " + search(root, 80));
}
private static class Node {
Node left;
int data;
Node right;
public Node(int data) {
this.data = data;
}
}
}
Output
The inorder traversal is 0 2 3 4 5 6 7
The preorder traversal is 4 2 0 3 5 6 7
Tree contains 3 : true
Tree contains 7 : true
Tree contains 80 : false
Tree contains 3 : true
Tree contains 7 : true
Tree contains 80 : false
Comments
Post a Comment