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).

• Each node will specified along with the values at its two children: e.g. (2:1,4) is a node whose left child has value 1 and right child has value 4 in it. If a node does not have a particular child then the value null will appear e.g. if a node with value 20 has a left child with value 5 and no right child, you will fine (20:5,null) in the input.
• There will be no specified order on the tuples given in the input i.e. you will not specifically be told what the root is. You will have to find the root by checking to see which value does not appear as a child of any other value e.g. consider: (10:7,12), (1:null,10), (7:null,null), (12:null,null). In this tree, the root is 1 because it has no parent.
• If the input does not constitute a valid binary tree your program should point out the error and say which node is not properly specified. Consider the example: (10:7,12), (1:null,10), (7:null,null). Here 12 appears as a child but the input doesn't specify what its children are. This is an error in the input and your program should catch it.

Implementation Notes:

• You have to take the input and make a binary tree out of it first and then check for the condition i.e. your assignment should contain a binary tree implementation and an algorithm for traversing the binary tree to check for the condition.
• You are allowed to read up on the binary tree implementation from the book but you have to type it in and test it yourself.
• The honor code must be follow for all assignments
• The program should work on linux with java 1.6 (You could test it on one of the computer center machines or one of the CSE general computing lab machines.)