Proof Let T be a binary search tree, and let S be a subtree of T. Let x
be any element oin S and let TL and TR be the left and right subtrees,
respectively, of x in S. Then since S is a subtree of T, x is also an element
of T, and TL and TR are left and right subtrees of x in T. Therefore,
y x z for every y 2 TL and every z 2 TR. Therefore, S too has the
Binary Search Tree (BST) property.
6