chap binary trees to figure to be binary search treethe left child of the node with value must have value between and fall within given range of values fortunatelyit requires only simple local calculation to determine which child(rento visit more difficult situation is illustrated by the following problem given an arbitrary binary tree we wish to determine iffor every node aare all nodes in ' left subtree less than the value of aand are all nodes in ' right subtree greater than the value of (this happens to be the definition for binary search treedescribed in section unfortunatelyto make this decision we need to know some context that is not available just by looking at the node' parent or children as shown by figure it is not enough to verify that ' left child has value less than that of aand that ' right child has greater value nor is it enough to verify that has value consistent with that of its parent in factwe need to know information about what range of values is legal for given node that information might come from any ancestor for the node thusrelevant range information must be passed down the tree we can implement this function as follows boolean checkbst(bstnode rootinteger lowinteger highif (root =nullreturn true/empty subtree integer rootkey root key()if ((rootkey high)return false/out of range if (!checkbst(root left()lowrootkey)return false/left side failed return checkbst(root right()rootkeyhigh) binary tree node implementations in this section we will examine ways to implement binary tree nodes we begin with some options for pointer-based binary tree node implementations then comes