BST Operations: Pseudocode (Part 1)

Introduction

We’ll now explore how to write algorithms on binary search trees. As we’ll see, we first need to understand the structure of the binary search tree (the links between nodes). Then, we need to understand how to write the algorithms to perform operations on the tree structure. These questions can be rephrased as follows:

• What is the structure of our tree?
• How can we manipulate the structure to obtain the desired result?
• We did the same for linked lists, where we made a few drawings before writing an algorithm. We first understood the structure of the list and how to manipulate it to obtain a result. After understanding the steps to perform, we translated them into code.

The findNode function

Given a BST root and a value, we must return the node from the tree which holds that particular value.

We already made a step-by-step example of finding a value in a BST when we compared the performance of BSTs and arrays.

Positive case

However, let’s go over one more example. Assume we want to find the node with the value 4 in the tree below. Follow the slides below: