Binary Search Tree Checking (for problems 13 and 14)

Binary Search Tree Checking (for problems 13 and 14)

This background is used by the next two problems: Given a plain binary tree, examine the tree to determine if it meets the requirement to be a binary search tree. To be a binary search tree, for every node, 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. Consider the following four examples...

a. 5 -> TRUE
/ \
2 7

b. 5 -> FALSE, because the 6 is not ok to the left of the 5
/ \
6 7

c. 5 -> TRUE
/ \
2 7
/
1

d. 5 -> FALSE, the 6 is ok with the 2, but the 6 is not ok with the 5
/ \
2 7
/ \
1 6

For the first two cases, the right answer can be seen just by comparing each node to the two nodes immediately below it. However, the fourth case shows how checking the BST quality may depend on nodes which are several layers apart -- the 5 and the 6 in that case.

13 isBST() -- version 1

Suppose you have helper functions minValue() and maxValue() that return the min or max int value from a non-empty tree (see problem 3 above). Write an isBST() function that returns true if a tree is a binary search tree and false otherwise. Use the helper functions, and don't forget to check every node in the tree. It's ok if your solution is not very efficient. (Thanks to Owen Astrachan for the idea of having this problem, and comparing it to problem 14)

Returns true if a binary tree is a binary search tree.

int isBST(struct node* node) {

14. isBST() -- version 2

Version 1 above runs slowly since it traverses over some parts of the tree many times. A better solution looks at each node only once. The trick is to write a utility helper function isBSTRecur(struct node* node, int min, int max) that traverses down the tree keeping track of the narrowing min and max allowed values as it goes, looking at each node only once. The initial values for min and max should be INT_MIN and INT_MAX -- they narrow from there.

/*
Returns true if the given tree is a binary search tree
(efficient version).
*/
int isBST2(struct node* node) {
return(isBSTRecur(node, INT_MIN, INT_MAX));
}

/*
Returns true if the given tree is a BST and its
values are > = min and < = max.
*/
int isBSTRecur(struct node* node, int min, int max) {

⇐ Предыдущая 123 Следующая ⇒