How to Search a Node in a Binary Search Tree

Share

Searching a node in a given Binary Search Tree is a process to search any existing node; let’s say if node A has to be searched then you got to follow below steps –

STEP 1: If there is no node in a given BST then return saying node A is not found as there is no node in the BST.

STEP 2: To find node A in a given Binary Search tree, just compare the value of node A with the root node’s value: 

if node A has a value greater than the root node’s value – traverse down the root node in its right node and Go to Step 2 by considering this right node as the root node (Note: if there is no right node straight go to Step 3)

if node A has a value lesser than the root node’s value – traverse down the root node in its left node and Go to Step 2 by considering this left node as the root node (Note: if there is no left node straight go to Step 3)

if node A has a equal to the root node’s value – it just means you have found the node – Just return the same saying Node A found in the Binary Search Tree.

STEP 3: Just return saying node A can not be deleted as it is not present in the BST.

Above Algorithm can be implemented using two popular ways – Recursive and an Iterative way

BST,java

package org.gontuseries.bst;

public class BST {

    private Node rootNode;

    public boolean contains(int value) {
        boolean found = false;

        found = contains(value, rootNode);
        return found;
 }

    private boolean contains(int value, Node currentNode) {
        boolean found = false;

        if (currentNode == null)
            return false;

        if (currentNode.getValue() < value) { 
            found = contains(value, currentNode.getRightNode());
        } else if (currentNode.getValue() > value) {
            found = contains(value, currentNode.getLeftNode());
        } else {
            found = true;
        }

        return found;
    }
}


package org.gontuseries.bst;

public class BST {

    private Node rootNode;

    private boolean contains(int value) {
        boolean found = false;
        Node currentNode = rootNode;

        while (true) {
            if (currentNode != null) {

                if (value > currentNode.getValue()) {
                    currentNode = currentNode.getRightNode();
                } else if (value < currentNode.getValue()) {
                    currentNode = currentNode.getRightNode();
                } else {
                    found = true; // Node found with the value
                    break;
                }
            } else {
                    System.out.println("Node not found with the value");
                    break;// Node not found with the value
            }
        }
        return found;
    }
}

Node.java


package org.gontuseries.bst;

public class Node {

    Node(int value) {
        this.value = value;
        this.leftNode = null;
        this.rightNode = null;
    }

    private int value;
    private Node leftNode;
    private Node rightNode;
    // --- writing all getters and setters for all properties 
    //i.e for value, leftNode, rightNode
}

Time Complexity: The run time complexity of search operation using Recursive way is: O(height of a Binary Search Tree) i.e O(h) [worst-case]

a) In case of a  skewed Binary Search Tree the height is equal to the number of nodes in it; so, it becomes O(n)[worst-case]

b) In case of a Binary Search Tree built using some Tree Balancing Techniques like AVL, RED Black etc the height is equal to log (number of nodes in it); so it becomes log(n) [worst-case]

where, ‘n’ is the number of nodes in a binary search tree.