Bit 9 Assign4

NUST School of Electrical Engineering and Computer Science Data Structures Assignment - 4 (BIT-9 A&B) Submission Date: Thursday, 26th June 2008, 1300 hrs MAX MARKS : 10 A: This assignment is to be done by each student individually. You are allowed to discuss the general concepts with other students, but these discussions must end the moment you start programming. B: 50% marks will be given for the complete correct code and rest of the marks will be given after the demonstration. C: This is ANONYMOUS assignment, therefore, your name should NOT appear on the assignment (NEITHER ON SOFT-COPY NOR ON HARD-COPY), only the registration number should be mentioned.

Deliverables: 1. Hard-copy in the Data Structures class on submission date. Each page must have your registration number on it. 2. Submit a soft-copy electronically on MyDropBox 3. Email a soft-copy having the subject “assignment4” on the following e-mail address: - [email protected] (for BIT-9A students) - [email protected] (for BIT-9B students) The name of the file (submitted on MyDropBox as well as the one sent via email) should be your complete registration number followed by your section. i.e. for example, 2007-NUST-BIT-999-A (WITHOUT any space in between) WARNING: • Assignment will not be considered, if the above rules are not followed. • Late assignment policy applies

Implement the following functions for a binary search tree. 1) LeafCount that takes the address of the root node of a tree as its parameter and returns the number of leaf nodes in the tree. 2) SingleParentCount that takes the address of the root node of a tree as its parameter and returns the number of nodes in the tree which have only one child. 3) LessNodeCount that takes the address of the root node of a tree, and an int value as its parameters and returns the count of nodes that contain a number less than the parameter value.

4) IsBST that takes the address of the root node of a tree as its parameter and returns true if the tree is a BST and false otherwise. NOTE: Use recursion in implementing these functions. HINT: You might find the tree traversal functions, given in slides, helpful in this problem.