#### Maylis

Gold Member

- 945

- 49

**1. The problem statement, all variables and given/known data**

Binary search trees

In these problems you will set up a binary search tree and write some associated functions that make

the search tree useful.

Loading the data file students.mat (downloaded with this assignment) places a cell array called

Students in the workspace. Students contains a list of student names and corresponding ID

numbers. In this first task, you will write a function to insert a student's name and ID number

into a binary search tree keyed to the ID numbers. Your function will have the declaration line

Code:

`function newTree = bstInsert(bst, rootInd, name, idNumber)`

1. bst: a structure array with fieldnames

##\bullet## name

##\bullet## ID

##\bullet## left

##\bullet## right

(very similar to what was described in the lecture videos) representing the binary search tree.

You may assume that the struct array is not empty and that the root of the binary search

tree is the first element of the array.

2. rootInd: the current root index

3. name: the name to be inserted into the search tree

4. idNum: the ID number to be inserted into the search tree

Remember that a new element with the name and ID number to be inserted must be appended

to the struct array bst before any elements of bst can be modied to point to its index.

The most natural way to write this function is with a recursive implementation that simply com-

pares the ID number to a current node, and based on the result of that comparison calls itself

recursively on the left or right subtree of the current node.

Note: For this problem, use the convention that if a key to be inserted is equal to an existing

key, the key to be inserted will be placed in the left subtree of the existing key.

The following code is useful for testing bstInsert. It initializes a binary search tree with the rst

row of the cell array Students and uses bstInsert to place the remainder of the student names

and ID numbers in the search tree.

Code:

```
load students;
studentTree = struct('name',Students{1,1},...
'ID',Students{1,2},...
'left',0,...
'right',0);
for k = 2:size(Students,1)
studentTree = bstInsert(studentTree,1,Students{k,1},Students{k,2});
end
```

lecture videos to view the elements of the binary search tree you create.

**2. Relevant equations**

**3. The attempt at a solution**

This is the given code for bstinorder

Code:

```
function bstinorder(tree,index)
% Print the part of a tree under index using inorder traversal
% Input the tree and the index
% Assumes the fields are 'key', 'left' and 'right'
% descend the left subtree
if tree(index).left ~=0
bstinorder(tree,tree(index).left)
end
% print current key when there is none smaller
disp(tree(index).key);
% descend the right subtree
if tree(index).right ~=0
bstinorder(tree,tree(index).right)
end
```

Code:

```
studentTree =
name: 'Jim'
ID: 19907875
left: 0
right: 0
```

Code:

```
function newTree = bstInsert(bst, rootInd, name, idNumber)
% Print the part of a tree under index using inorder traversal
% Input the tree and the index
% Assumes the fields are 'key', 'left' and 'right'
% descend the left subtree
if bst(rootInd).left ~= 0
newTree = bstInsert(bst,bst(rootInd).left,bst(rootInd).name,bst(rootInd).idNumber);
end
% print current key when there is none smaller
disp(bst(rootInd).name);
% descend the right subtree
if bst(rootInd).right ~= 0
newTree = bstInsert(bst,bst(rootInd).left,bst(rootInd).name,bst(rootInd).idNumber);
end
```

Code:

```
Error in bstInsert (line 7)
if bst(rootInd).left ~=0
Output argument "newTree" (and maybe others) not assigned
during call to
"C:\Users\Owner\Documents\MATLAB\bstInsert.m>bstInsert".
```