When dealing with trees, algorithm complexity is usually measured in terms of th
ID: 3825948 • Letter: W
Question
When dealing with trees, algorithm complexity is usually measured in terms of the number of nodes in the tree while the elementary operation is usually a node traversal. Let T be a binary tree such that each node u has a parent , rightChild and leftChild and a key element, key . The left/right child may be null indicating it does not exist. Given a binary tree, we wish to determine if it is a binary search tree or not.
(a) Gomer thinks we can solve this problem by using a preorder traversal. When each node u is processed, it simply verifies that the left child’s key is strictly less than u’s key and u’s right child’s key is strictly greater than u’s key. Gomer’s solution, however, will not work. Provide a counter example to demonstrate this and explain how it shows Gomer is wrong.
(b) Design a correct algorithm that, given a root note in a binary tree (with parent , rightChild , leftChild and key elements) determines if it is a binary search tree or not. Fully analyze your algorithm.
Explanation / Answer
a) To be a binary search tree, for every node 'u', all of the nodes in its left tree must be <= the node, and all of the nodes in its right subtree must be > the node not just its left child and right child. So obvisously Gomer's solution wont work.
Counter example to prove Gomer's solution wont work:
5
/
2 7
/
1 6
The above tree is not a binary search tree because: the 6 is ok with the 2, but the 6 is not ok with the 5.
b) The good way to check if the given binary tree is binary search tree is to remember, at each node u, the minimum node seen so far and the maximum node seen so far. This is resolve the above mentioned issue since we now have minimum and maximum so far. Instead of just checking left child and right child with parent we can evaluate the value with respective to the minimum and maximum as well. Below is the code.
/*
Returns true if the given tree is a binary search tree.
*/
int isBinarySearchTree(struct node* node) {
return(isBST(node, INT_MIN, INT_MAX));
}
/*
Returns true if the given tree is a binary search tree and its
values are >= min and <= max.
*/
int isBST(struct node* node, int min, int max) {
if (node == NULL) return(true);
// false if this node violates the min/max constraint
if (node->data < min || node->data > max) return(false);
// otherwise check the subtrees recursively,
// updating the min or max constraint
return
isBST(node->left, min, node->data) &&
isBST(node->right, node->data + 1, max)
);
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.