An important special kind of binary tree is the binary search tree (BST). In a BST, each node stores some information including a unique key value and perhaps some associated data. A binary tree is a BST iff, for every node n, in the tree:



All keys in n s left subtree are less than the key in n, and

all keys in n s right subtree are greater than the key in n.