# How to Search a Node in a Binary Search Tree

**Recommended to visit before going through this article:**

**What is a Binary Search Tree? How to represent it ? And, related terminologies…**

**How to insert a node in a Binary Search Tree ?**

**How to delete a node in a Binary Search Tree ?**

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.