Question 1 (10 marks)
One question on tree algorithms, for example,
- Implement function isBalanced(BSTree t) that returns 1 if a given tree is balanced; zero otherwise. We say a tree is balanced if for every node in the tree, the difference between the number of nodes in the left sub-tree and the number of nodes in the right sub-tree must not be greater than one. A tree with no nodes is considered to be balanced. Please note that the criterion is (slightly) different to a height balanced tree.
- Implement function countNodes(BSTree t) that counts and returns number of nodes in a given tree.
- Implement function countLeaf(BSTree t) that counts and returns number of leaf nodes in a given tree.
- Implement function height(BSTree t) that finds and returns height of a given tree.
- Implement function countOdds(BSTree t) that counts and returns number of nodes in a given tree with odd key values.