Searching in a Binary Search Tree (Implementation)

Explore how to implement both iterative and recursive search methods in a binary search tree using C#. Understand the algorithm to traverse the tree for matching values, and gain insight into time complexities for average and worst cases. This lesson builds skills to efficiently retrieve nodes in tree data structures.

We'll cover the following...

- Introduction
- Iterative search implementation
- - Putting into the BinarySearchTree class
- - Explanation
- Recursive search implementation
- - Putting into the BinarySearchTree class
- - Explanation
  - Time complexity

Introduction

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

Here is a high-level description of the algorithm:

Set the currentNode equal to root.
If the value is less than the currentNode's value, then move on to the left-subtree. Otherwise, move on to the right-subtree.
Repeat until the value at the currentNode is equal to the value searched, or it becomes NULL.
Return the currentNode. ...

1.Introduction to Complexity Measures

2.Introduction to Arrays

3.Introduction to Linked Lists

4.Introduction to Stack/Queues

5.Introduction to Graphs

6.Introduction to Trees

7.Trie

8.Introduction to Heap

9.Introduction to Hashing

10.Summary of Data Structures

Searching in a Binary Search Tree (Implementation)

Introduction