Search in Binary Search Trees (Implementation)
Explore how to implement search functionality in binary search trees using Java. Learn both iterative and recursive methods, understand the traversal logic, and analyze the average and worst-case time complexities to improve your coding skills for interviews.
Introduction
In this lesson, we are going to implement the Search functionality by using the BST class. The following are the steps that we perform to search for an element in BST.
- Start from Root.
- If the value is less than the current node value, then traverse the left sub-tree; if it is more, then traverse the right sub-tree.
- Keep on doing the above step until you either find a
nodewith that value or reach a leafnode—in which case the value doesn’t exist in the Binary Search Tree.
Iterative Search Implementation
Explanation
The search() function is implemented in lines 17-35 in binarySearchTree.java file. We take advantage of the property of BST in this function. If the given value is less than the value of currentNode then we only search in the left sub-tree of the currentNode, or else we search in the right. We repeat this until either the node is ...