Search in binary tree


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

Popular posts from this blog

SQL basic interview question

gsutil Vs Storage Transfer Service Vs Transfer Appliance