Searching in a Binary Search Tree (Implementation)

This lesson is about Searching in Binary Search Tree and how to implement searching functionality in C++.

We'll cover the following

Introduction #

In this lesson, we’ll implement a search function for binary search trees, which will return a node from the tree if the value to be searched matches it. We’ll again implement both an iterative and a recursive solution.

Here is a high-level description of the algorithm:

  1. Set the current node equal to root.

  2. If the value is less than the current node's value, then move on to the left subtree, otherwise move on to the right sub-tree

  3. Repeat until the value at the current node is equal to the value searched, or it becomes NULL.

  4. Return the current node

Iterative Search Implementation #

Level up your interview prep. Join Educative to access 80+ hands-on prep courses.