Question

a) Design a recursive linear-time algorithm that tests whether a binary tree is a binary search tree. Describe your algorithm in English or with a simple pseudocode program. b) (3 bonus pts.) Extend the algorithm in a) to test whether a binary tree is an AVL tree.

Answer 1

**Here is the algorithm that checks that a Binary tree is a binary search tree or not -

function BST()

if(root == null)

return 1

if(root -> left != null && maxValue(root -> left) > root -> data)

return 0

if(root -> right != null && maxValue(root -> right) > root -> data)

return 0

if(!BST(root -> left) || !BST(root -> right))

return 0

return 1

**Here is the algorithm that checks that Binary tree is an AVL tree or not -

function AVL()

if(root == null)

return 1

left_height = height(root -> left)

right_height = height(root -> right)

if(abs (left_height - right_height) <= 1 && AVL(root -> left) && AVL(root -> right))

return 1

return 0