IntegerComparator

*"More output"*

**Algorithm** isBST(*tree*):

*Input:* a binary tree whose nodes contains keys

*Output:* (Is *tree* a binary search tree?,
minimal key stored in *tree*, maximal key stored in *tree*)

**if** *tree* has one node **then**

*result* (true, key of root of *tree*, key of root of *tree*)

**else**

(*isBST*_{left}, *min*_{left}, *max*_{left})
isBST(left subtree of *tree*)

(*isBST*_{right}, *min*_{right}, *max*_{right})
isBST(right subtree of *tree*)

*isBST*
*isBST*_{left} *isBST*_{right}
*max*_{left} <= key of root of *tree* <= *min*_{right}

*min* min(key of root of *tree*, *min*_{left}, *min*_{right})

*max* min(key of root of *tree*, *max*_{left}, *max*_{right})

*result* (*isBST*, *min*, *max*)

**return** *result*

*"More input"*

**Algorithm** isBST(*tree*, *min*, *max*):

*Input:* a binary tree whose nodes contains keys; key; key

*Output:* Is *tree* a binary search tree?
(A *node* : *node* is a node of *tree* : *min* <= key of *node* <= *max*)

**if** *tree* has one node **then**

*result* *min* <= key of root of *tree* <= *max*

**else**

*result*
*min* <= key of root of *tree* <= *max*
isBST(left subtree of *tree*, *min*, min(key of root of *tree*, *max*))
isBST(right subtree of *tree*, max(*min*, key of root of *tree*), *max*)

**return** *result*

*Implementation of a binary tree by means of an array*

**Algorithm** removeAboveExternal(*node*):

*Precondition:* *node* is external and different from the root

*Input:* a node of the binary tree

*Postcondition:* *node* and its parent have been removed from the tree
and the sibling of *node* takes the place of its parent

*Output:* the element of the parent of *node*

*index* index of *node*

*parent* *index* div 2

*element* element of *tree*[*parent*]

*sibling* *index* + 1 - 2 * (*index* mod 2)

move(*sibling*, *parent*)

*size* *size* - 2

**return** *element*

**Algorithm** move(*old*, *new*):

*Precondition:* *old* is the index of a child of the node with index *new*

*Input:* two indices of nodes

*Postcondition:* the subtree rooted at node with index *old* replaces the subtree rooted at node with index *new*

*tree*[*new*] *tree*[*old*]

**if** *tree*[*old*] is an internal node **then**

move(2 * *old*, 2 * *new*)

move(2 * *old* + 1, 2 * *new* + 1)

**else**

tree[2 * *new*] empty

tree[2 * *new* + 1] empty