Contents

# Binary Search Trees

## Synopsis

A binary search tree is a binary tree where the nodes in the tree are ordered by ther values. Usually nodes on the left side are "less than" than those on the right side of the tree, recursively. When we say a node A is less than a node B, we mean the value stored at node A is less than the value stored at node B. More specifically, the following rules apply at any point in the tree.

• a left-child node is less than or equal to its parent
• a right-child node is equal to or greater than its parent

## Structure

```    class binaryTreeNode
{
var value;
var left;
var right;
var parent;            //optional
}

class binarySearchTree
{
var root;               //the top-level binary tree node
// operations
...
}
```

## Vocabulary

The terms used in describing a binary search tree are the same as those describing a generic binary tree.

## Supports

Binary search trees are considered top-level data structures.

## Dependencies

Binary search trees are based upon tree nodes.

## Operations

The operation descriptions assume unique values in the tree, with values to the left less than those to the right. For trees with duplicate values or a reversed ordering, appropriate modifications to the descriptions should be made.

### insert

The typical insertion strategy looks like this:

• create a node n containing the given value to insert
• call a helper function with the root and node n

The helper function implements this straegy, with current referring to its first argument and n refering to the second:

```    if node n is less than the current node //n must belong on left side of tree
if the current node has no left child
set the left child pointer of the current node to n
else
recur, passing the left child and n to the helper
else //n must belong on right side of tree
if the current node has no right child
set the right child pointer of the current node to n
else
recur, passing the right child and n to the helper
```

A special case exists if the tree is empty, since the root pointer will need to be set. Inserting a value into a binary tree can take linear time, if the tree is pathologically unbalanced.

### delete

There are a number of deletion strategies. One that preserves the existing balance of the tree to some degree is as follows...

## Traversals

Traversals for binary search trees are the same as those of binary trees.

## Concept Inventory

1. Consider a binary search tree with n nodes. What is the best case time complexity for finding a value at a leaf?
1. constant
2. log n
3. sqrt(n)
4. linear
5. n log n

2. Consider a binary search tree with n nodes. What is the worst case time complexity for finding a value at a leaf?
1. constant
2. log n
3. sqrt(n)
4. linear
5. n log n

3. Which ordering of input values builds the most unbalanced BST? Assume values are inserted from left to right.
1. 2
2. 3
3. 1

4. Which ordering of input values builds the most balanced BST? Assume values are inserted from left to right.
1. 5
2. 7
3. 8

5. For all child nodes in a BST, what relationship holds between the value of a child node and the value of its parent?
1. greater than or equal to
2. less than or equal to
3. greater than or equal to, if the child is a right child
4. less than or equal to, if the child is a right child
5. there is no relationship

6. For all sibling nodes in a BST, what relationship holds between the value of a left child node and the value of its sibling?
1. greater than or equal to
2. less than or equal to
3. equal to
4. there is no relationship

7. Do all these deletion strategies for non-leaf nodes reliably preserve BST ordering?
• Swap the values of the node to be deleted and the smallest leaf node with a larger value, then remove the leaf.
• Swap the values of the node to be deleted with its predecessor or successor. If the predecessor or successor is a leaf, remove it. Otherwise, repeat the process.
• If the node to be deleted does not have two children, simply connect the parent's child pointer to the node to the node's child pointer, otherwise, use a correct deletion strategy for nodes with two children.
1. true
2. false

lusth@cs.ua.edu

 Contents