Binary Search Tree
Also Called ordered or sorted binary tree. 1. The X node's left child and all of its descendants have lower values than X's value. 2. The right child, and all its descendants have higher values than X's value. 3. Left and right subtrees must also be Binary Search Trees. 4. Unique keys.
Concepts
- height: maximal number of levels below the root
How to Construct Binary Search Tree(BST)
sort first, recursively selecting the middle element as the root, with the left half forming the left subtree.