# 9.5 BinarySearchTree¶

BinarySearchTree(R) is the domain of binary trees with elements of type R, ordered across the nodes of the tree. A non-empty binary search tree has a value of type R, and right and left binary search subtrees. If a subtree is empty, it is displayed as a period (.).

Define a list of values to be placed across the tree. The resulting tree has 8 at the root; all other elements are in the left subtree.

```
lv := [8,3,5,4,6,2,1,5,7]
```

[8,3,5,4,6,2,1,5,7] |

_{Type: List PositiveInteger}

A convenient way to create a binary search tree is to apply the operation binarySearchTree to a list of elements.

```
t := binarySearchTree lv
```

[[[1,2,.],3,[4,5,[5,6,7]]],8,.] |

_{Type: BinarySearchTree PositiveInteger}

Another approach is to first create an empty binary search tree of integers.

```
emptybst := empty()$BSTREE(INT)
```

[] |

_{Type: BinarySearchTree Integer}

Insert the value 8. This establishes 8 as the root of the binary search tree. Values inserted later that are less than 8 get stored in the left subtree, others in the right subtree.

```
t1 := insert!(8,emptybst)
```

8 |

_{Type: BinarySearchTree Integer}

Insert the value 3. This number becomes the root of the left subtree of t1. For optimal retrieval, it is thus important to insert the middle elements first.

```
insert!(3,t1)
```

[3,8,.] |

_{Type: BinarySearchTree Integer}

We go back to the original tree t. The leaves of the binary search tree are those which have empty left and right subtrees.

```
leaves t
```

[1,4,5,7] |

_{Type: List PositiveInteger}

The operation split(k,t) returns a record containing the two subtrees: one with all elements less than k, another with elements greater than k.

```
split(3,t)
```

[less=[1,2,.],greater=[[.,3,[4,5,[5,6,7]]],8,.]] |

_{Type: Record(less: BinarySearchTree PositiveInteger,greater:}
BinarySearchTree PositiveInteger)

Define insertRoot to insert new elements by creating a new node.

```
insertRoot: (INT,BSTREE INT) -> BSTREE INT
```

_{Type: Void}

The new node puts the inserted value between its less tree and greater tree.

```
insertRoot(x, t) ==
a := split(x, t)
node(a.less, x, a.greater)
```

Function buildFromRoot builds a binary search tree from a list of elements ls and the empty tree emptybst.

```
buildFromRoot ls == reduce(insertRoot,ls,emptybst)
```

_{Type: Void}

Apply this to the reverse of the list lv.

```
rt := buildFromRoot reverse lv
```

[[[1,2,.],3,[4,5,[5,6,7]]],8,.] |

_{Type: BinarySearchTree Integer}

Have FriCAS check that these are equal.

```
(t = rt)@Boolean
```

true |

_{Type: Boolean}