# Operations on a binary search tree

## Contents

# 16.2. Operations on a binary search tree#

In this section, we will discuss how to how to **print** the values of the nodes in order in a binary search tree, how to **search** for and **insert** elements in a binary search tree. We will **not** discuss how to delete elements from a binary search tree.

## 16.2.1. Preliminaries#

Recall that a binary search tree can be represented using the following data structure `BSTree`

that only holds a pointer to the `root`

of the binary search tree. While each node in the binary search tree can be represented using the following data structure `Node`

that holds the `data`

of the node, and pointers to the `left`

and `right`

children of the node.

```
typedef struct bstree {
Node *root;
} BSTree;
```

```
typedef struct node {
int data;
struct node *left;
struct node *right;
} Node;
```

## 16.2.2. Create a node in a binary search tree#

Similar to the linked list, we can create a node in a binary search tree using the following function `createNode`

that takes in the `value`

of the node to be created, and returns a pointer to the newly created node.

**Code**

To use this function to create a node in a binary search tree, we can do the following:

**Code**

Note

Recall here that `tree`

is not a pointer, it is a variable of type `BSTree`

. So, when we access `root`

of the binary search tree, we need to use the `.`

operator. However, when we access the `data`

of the `Node* p`

in `createNode`

function, we need to use the `->`

operator, since `p`

is a pointer to a `Node`

.

## 16.2.3. Printing the values of the nodes in order#

Recall that all elements on the left subtree are smaller than the root, and all elements on the right subtree are larger than the root. To print the values of the nodes in a binary search tree in order, we have to printing the values of the nodes in the left subtree, then printing the value of the root, and finally printing the values of the nodes in the right subtree.

If we start by printing the nodes in the left subtree, we still have to print nodes in the left subtree of the left subtree first, then its root, then the right subtree of the left subtree. For example, in the following figure, we show the order of nodes we have to traverse to print the values of the nodes in order.

If we start from the root, we can traverse the left node, then the left node of that and so on till we reach the leftmost node and print it. To able to go back to all the nodes back up to the root, we must have a way to keep track of the nodes we have visited. We can make use of recursive functions to keep track of the nodes we have visited. Recall that recursive functions are functions that call themselves, and store the values of their local variables in the stack, independent of the values of the local variables in the other instances of the function.

Therefore, we can use recursion to print the values of the nodes in order. We need to think of two things: the recursive call and the base case. The recursive call is the call to the function itself, and the base case is the case where we do not need to make a recursive call. To find the recursive call, we need to **think recursively**, or think of a smaller sized problem to the current problem. The current problem is to print the entire tree, and a smaller problem can be a smaller subtree. Refer to the following figure to see how we can think recursively to print the values of the nodes in order.

If we start from the root, we can call the print function on the left subtree first, then print the root, and finally call the print function on the right subtree.

We can use the following helper function `printHelper`

to recursively print the values of the nodes in order.

**Code**

```
1void printHelper(Node *n) {
2 if (n == NULL) {
3 return; // Base case.
4 }
5
6 // Print all smaller values first.
7 printHelper(n->left); // Recursive call.
8
9 // Print the parent node.
10 printf("%d ", n->data);
11
12 // Print all larger values next.
13 printHelper(n->right); // Recursive call.
14}
```

In lines \(2\) to \(4\), we have our base case, which is when we reach a node that is `NULL`

.

We call the preceding function on the root of the binary search tree inside the following function `print`

. The following function receives a pointer `tree`

to the binary search tree data structure.

**Code**

```
void print(BSTree *tree) {
// Starting from the root, recursively traverse and print the tree in-order.
printHelper(tree->root);
}
```

### 16.2.3.1. Tracing the print function#

We will trace the `printHelper`

function on the following small tree.

The following figure shows the order of function calls when `printHelper`

function is called on the root of the tree. Note that the function calls are stored in the stack, and the function calls store different values of `n`

in the stack. When a function returns, it returns to where it was called in the calling function, and the values of the local variables are restored to the values they had when the function call was made.

## 16.2.4. Search for a node with a given value#

Searching for a node in a binary search tree is easier than printing nodes, because printing nodes requires us to traverse the entire tree, while searching for a node requires us to traverse only a part of the tree as we will show now.

For example, we are to look for the node with the value \(10\) in the following tree. Looking for `10`

in the tree is similar to looking for `10`

in a sorted array. We can start from the root, `8`

is smaller than `10`

, hence `10`

should be in the right subtree. To the right of `8`

, we have `11`

, which is larger than `10`

, hence `10`

should be in the left subtree of `11`

. To the left of `11`

, we have `10`

, which is equal to `10`

, hence we have found the node we are looking for.

However, if we were looking for `9`

in the tree, we have to go to the right of `8`

, then left of `11`

, then left of `10`

, then we find `NULL`

. At this point, we can conclude that `9`

is not found. If `9`

was there, it should have been to the left of `10`

.

In summary, we can start from the root, and compare the value of the root with the value we are looking for. If the value of the root is smaller than the value we are looking for, we can search for the value in the right subtree. If the value of the root is larger than the value we are looking for, we can search for the value in the left subtree. If the value of the root is equal to the value we are looking for, we have found the node we are looking for. If we reach a `NULL`

node, we can conclude that the value we are looking for is not found.

### 16.2.4.1. Iterative search#

Since we are only traversing one branch of the tree, we only need to keep track of one node at a time. Therefore, we can use a non-recursive function to search for a node with a given value.

We can use the following function `search`

to search for a node with a given value. The following function receives a pointer `tree`

to the binary search tree data structure, and a value `value`

to search for. The function returns a pointer to the node with the given value, or `NULL`

if the value is not found.

**Code**

```
1Node *search(BSTree *tree, int value) {
2 Node *current = tree->root;
3
4 while (current != NULL && current->data != value) {
5 // We have not found the value yet.
6 if (value < current->data) {
7 // Check the left subtree.
8 current = current->left;
9 } else {
10 // Check the right subtree.
11 current = current->right;
12 }
13 }
14
15 // Note: current can be NULL if the value is not found.
16 return current;
17}
```

Line \(4\) is the condition for the loop to keep iterating. Of course, we need to keep traversing a branch of the tree if we have not found the value yet, hence we should keep iterating as long as `current->data`

is not `value`

. However, it will cause a segmentation fault if we try to access `current->data`

when `current`

is `NULL`

. Therefore, we also need to check that `current`

is not `NULL`

. Checking for `current != NULL`

should be before checking for `current->data != value`

, because if `current`

is `NULL`

, we cannot access `current->data`

. Hence, the condition for the loop to keep iterating is `current != NULL && current->data != value`

. Recall that lazy evaluation is used in C, hence the second condition will not be evaluated if the first condition is `false`

.

When we exit the loop, either `current`

is pointing to the node we are looking for, or `current`

is `NULL`

if the value is not found. Hence, we can return `current`

as the result of the function.

### 16.2.4.2. Recursive search#

We can also write a recursive function to search for a node with a given value. The following function `searchRecursiveHelper`

is a helper function that receives a pointer `n`

to the current node, and a `value`

to search for. The function returns a pointer to the node that was found, or `NULL`

if the node was not found.

**Code**

```
1Node *searchRecursiveHelper(Node *n, int value) {
2 if (n == NULL) {
3 // Nothing left to explore.
4 return n; // Base case.
5 }
6
7 if (n->data == value) {
8 // Found the node.
9 return n; // Base case (can combine with above if-statement).
10 }
11
12 // At this point, n is non-NULL.
13 // Also, n is not the node we are looking for.
14
15 if (value < n->data) {
16 // Check the left subtree.
17 return searchRecursiveHelper(n->left, value);
18 } else {
19 // Check the right subtree.
20 return searchRecursiveHelper(n->right, value);
21 }
22}
```

Lines \(15\) - \(21\) look into the `data`

of node `n`

and decide which subtree to explore. If `value < n->data`

is `true`

, we explore the left subtree and call `searchRecursiveHelper(n->left, value)`

. Otherwise, we explore the right subtree and call `searchRecursiveHelper(n->right, value)`

.

The recursive calls continue until we reach a `NULL`

node, or we find the node we are looking for. These are our terminating conditions or base cases.

Lines \(2\) - \(5\) and \(7\) - \(10\) are the base cases. If `n`

is `NULL`

, we have reached a `NULL`

node, and we can conclude that the value we are looking for is not found. If the value of `n`

is equal to the value we are looking for, we have found the node we are looking for. In both cases, we return `n`

.

The following function `searchRecursive`

is a wrapper function that receives a pointer `tree`

to the binary search tree data structure, and a value `value`

to search for. The function returns a pointer to the node that was found, or `NULL`

if the node was not found. This happens by calling `searchRecursiveHelper`

on the root node of the tree.

**Code**

```
Node *searchRecursive(BSTree *tree, int value) {
// Start at the root and traverse the tree recursively.
return searchRecursiveHelper(tree->root, value);
}
```

## 16.2.5. Inserting a node with a given value#

Inserting a node with a given value is a similar to searching for a node with a given value. For example, given the following binary search tree, we want to insert a node with value `9`

.

We have to start from the root, and compare the value of the root, which is

`8`

and`9`

.Since

`9`

is larger than`8`

, we can insert the node in the right subtree.Looking at the right node of

`8`

, we see that its value is`11`

, which is larger than`9`

. Hence, we can insert the node in the left subtree of`11`

.Looking at the left node of

`11`

, we see that it is`10`

, hence we can insert the node in the left subtree of`10`

.Looking at the left node of

`10`

, we see that it is`NULL`

, hence we can insert the node in the left subtree of`NULL`

.

We can only insert a node at an empty place in the tree. Therefore, we need to traverse the tree until we reach a `NULL`

node. It can be a leaf node or a node
with only one child.

### 16.2.5.1. Iterative insertion#

We can use the following function `insert`

to insert a node with a given value. The following function receives a pointer `tree`

to the binary search tree data structure, and a value `value`

to insert. The function returns a `bool`

value, which is `true`

if the node that was inserted, or `false`

if the node was not inserted.

Similar to the `search`

function, we can have a `current`

pointer that points to the current node. We can stop traversing the node when `current`

is `NULL`

, which is where the node should be inserted. However, we need a pointer to the parent node to point its `right`

or `left`

to the new node inserted. This is why we additionally need a `parent`

pointer that points to the parent of the `current`

node.

We start at the root node, and traverse the tree using `current`

and `parent`

until `current`

reaches a `NULL`

node. At each iteration, we update the `current`

and `parent`

pointers. `current`

moves to the left or right subtree depending on the value of `value`

. `parent`

is always the parent of `current`

.

When we exit the loop, `current`

is `NULL`

, and `parent`

is the parent of the node we want to insert. We can insert the node in the left or right subtree of `parent`

depending on the value of `value`

.

**Draft Code**

```
bool insert(BSTree *tree, int value) {
// The tree is not empty.
Node *current = tree->root; // The current subtree.
Node *parent = NULL; // the root node has no parent.
while (current != NULL) {
parent = current;
if (value < current->data) {
// The new node should go to the left of the current subtree.
current = current->left;
} else {
// The new node should go to the right of the current subtree.
current = current->right;
}
}
// At this point, current is NULL.
// But also, we know that we need to insert to the right/left of parent.
if (value < parent->data) {
// The new node should go to the left of the parent.
parent->left = createNode(value);
return parent->left != NULL;
} else {
// The new node should go to the right of the parent.
parent->right = createNode(value);
return parent->right != NULL;
}
}
```

The special case of this function is if the tree is empty. In this case, we can simply create a new node and assign it to the root of the tree. We tackle this case in the following function `insert`

from lines \(1\) - \(5\).

**Code**

```
1bool insert(BSTree *tree, int value) {
2 if (tree->root == NULL) {
3 // The tree is empty, add its first node.
4 tree->root = createNode(value);
5 return tree->root != NULL;
6 }
7
8 // The tree is not empty.
9 Node *current = tree->root; // The current subtree.
10 Node *parent = NULL; // the root node has no parent.
11
12 while (current != NULL) {
13 parent = current;
14
15 if (value < current->data) {
16 // The new node should go to the left of the current subtree.
17 current = current->left;
18 } else {
19 // The new node should go to the right of the current subtree.
20 current = current->right;
21 }
22 }
23
24 // At this point, current is NULL.
25 // But also, we know that we need to insert to the right/left of parent.
26
27 if (value < parent->data) {
28 // The new node should go to the left of the parent.
29 parent->left = createNode(value);
30
31 return parent->left != NULL;
32 } else {
33 // The new node should go to the right of the parent.
34 parent->right = createNode(value);
35
36 return parent->right != NULL;
37 }
38}
```

Note

We are making an assumption that before calling `insert`

, we have checked that the value we are inserting is not already in the tree. If the value is already in the tree, we should not insert it again.

### 16.2.5.2. Recursive insertion#

We can also implement the `insert`

function recursively. The following function `insertRecursiveHelper`

receives a pointer `n`

to the current node, and a value `value`

to insert. The function returns a pointer to the root node.

We can use the same logic as the iterative function. We start at the root node, and recursively traverse the right or left subtree depending on the value of the node `n`

and `value`

we want to insert until we reach a `NULL`

node. Our recursive call updates the `n`

pointer: `n`

moves to the left or right child depending on the value of `value`

.

At some point in time, we find `n`

is `NULL`

. This is when we exit the recursion and create the node. We return the pointer to the node that we created. This pointer is then assigned to the `left`

or `right`

pointer of the parent node.

The following code implements the insert function recursively. To help understand the function, we trace the execution of the function for the following tree in Fig. 16.2.

**Code**

```
Node *insertRecursiveHelper(Node *n, int value) {
if (n == NULL) {
// We have reached an empty spot in the tree, create the node.
return createNode(value); // Base case.
}
if (value < n->data) {
// The new node should go to the left of the current subtree.
n->left = insertRecursiveHelper(n->left, value); // Recursive call.
} else {
// The new node should go to the right of the parent.
n->right = insertRecursiveHelper(n->right, value); // Recursive call.
}
return n;
}
```

The following `insertRecursive`

function is a wrapper function that calls `insertRecursiveHelper`

and updates the `tree->root`

of the tree if `insertRecursiveHelper`

returns a pointer to the a new root. There is a new root when the `root`

of the tree was pointing to `NULL`

, and the new node is inserted at the `root`

. The function returns `true`

if the node was inserted successfully, and `false`

otherwise.

**Code**

```
bool insertRecursive(BSTree *tree, int value) {
// Start at the root and recursively traverse the tree.
Node *inserted = insertRecursiveHelper(tree->root, value);
// The root of the tree may have been updated.
tree->root = inserted;
return inserted != NULL;
}
```

### Quiz

0 Questions