Binary Search Tree

Chapter 12: Binary Search Trees

A binary search tree is a binary tree with a

special property called the BST-property,

which is given as follows:

?

For all nodes x and y, if y belongs to the

left subtree of x, then the key at y is less

than the key at x, and if y belongs to the

right subtree of x, then the key at y is

greater than the key at x.

We will assume that the keys of a BST are

pairwise distinct.

Each node has the following attributes