binary tree search

1/* This is just the seaching function you need to write the required code.
2	Thank you. */
3
4void searchNode(Node *root, int data)
5{
6    if(root == NULL)
7    {
8        cout << "Tree is empty\n";
9        return;
10    }
11
12    queue<Node*> q;
13    q.push(root);
14
15    while(!q.empty())
16    {
17        Node *temp = q.front();
18        q.pop();
19
20        if(temp->data == data)
21        {
22            cout << "Node found\n";
23            return;
24        }
25
26        if(temp->left != NULL)
27            q.push(temp->left);
28        if(temp->right != NULL)
29            q.push(temp->right);
30    }
31
32    cout << "Node not found\n";
33}

1Binary Search Tree is a node-based binary tree data structure which has the following properties:
2
3The left subtree of a node contains only nodes with keys lesser than the node’s key.
4The right subtree of a node contains only nodes with keys greater than the node’s key.
5The left and right subtree each must also be a binary search tree.
6

1public class BinarySearchTree {
2
3    public class Node {
4        //instance variable of Node class
5        public int data;
6        public Node left;
7        public Node right;
8
9        //constructor
10        public Node(int data) {
11            this.data = data;
12            this.left = null;
13            this.right = null;
14        }
15    }
16    
17    // instance variable
18    public Node root;
19
20    // constructor for initialise the root to null BYDEFAULT
21    public BinarySearchTree() {
22        this.root = null;
23    }
24
25    // insert method to insert the new Date
26    public void insert(int newData) {
27        this.root = insert(root, newData);
28    }
29
30    public Node insert(Node root, int newData) {
31        // Base Case: root is null or not
32        if (root == null) {
33            // Insert the new data, if root is null.
34            root = new Node(newData);
35            // return the current root to his sub tree
36            return root;
37        }
38        // Here checking for root data is greater or equal to newData or not
39        else if (root.data >= newData) {
40            // if current root data is greater than the new data then now process the left sub-tree
41            root.left = insert(root.left, newData);
42        } else {
43            // if current root data is less than the new data then now process the right sub-tree
44            root.right = insert(root.right, newData);
45        }
46        return root;
47    }
48
49    // method for search the data , is data is present or not in the tree ?
50    public boolean search(int data) {
51        return search(this.root, data);
52    }
53
54    private boolean search(Node root, int data) {
55        if (root == null) {
56            return false;
57        } else if (root.data == data) {
58            return true;
59        } else if (root.data > data) {
60            return search(root.left, data);
61        }
62        return search(root.right, data);
63    }
64
65    //Traversal
66    public void preorder() {
67        preorder(root);
68        System.out.println();
69    }
70
71    public void preorder(Node root) {
72        if (root == null) {
73            return;
74        }
75        System.out.print(root.data + " ");
76        preorder(root.left);
77        preorder(root.right);
78    }
79
80    public static void main(String[] args) {
81        // Creating the object of BinarySearchTree class
82        BinarySearchTree bst = new BinarySearchTree();
83        // call the method insert
84        bst.insert(8);
85        bst.insert(5);
86        bst.insert(9);
87        bst.insert(3);
88        bst.insert(7);
89        bst.preorder();
90        System.out.println(bst.search(7));
91        
92    }
93}
94

1# Driver Code 
2arr = [ 2, 3, 4, 10, 40 ] 
3x = 10
4  
5# Function call 
6result = binarySearch(arr, 0, len(arr)-1, x) 
7  
8if result != -1: 
9    print ("Element is present at index % d" % result) 
10else: 
11    print ("Element is not present in array")