Assignment 3: Binary Search Tree

Due: Sep 24, 11.55PM

(Submit at moodle.)

Suppose you are given a binary tree which has (all distinct) integer values in its nodes. We say it is a binary search tree if all the numbers in the right subtree of a node have values greater than the root and all the numbers in the left subtree have values smaller than the root (as discussed in class).

In this assignment you will be given a binary tree with numbers at nodes and you will have to check if the binary satisfies the condition of being a binary search tree.

NOTE: If the tree is not a binary search tree your program should point out where the condition fails i.e. it should return the value at a given node and another value from either its left subtree (which is greater than the value at the node) or its right subtree (which is less than the value at the node).

The input will be given by file. The format will be as follows:

Implementation Notes: