Binary Search Trees

Compare the search and update costs of unsorted lists and sorted arrays to identify the need for a dynamic ordered-search structure.

Summarize the development of binary search trees from binary-search ideas through early algorithms such as Hibbard deletion and the later need for balanced variants.

State the strict binary search tree ordering invariant for a no-duplicate key policy.

Determine whether a labeled binary tree satisfies the BST ordering invariant.

Derive the time and auxiliary-space cost of a BST operation from the tree's height.

Implement a minimal parent-free BST node and tree container in Java.