Binary Search Trees

Using CLRS:

• A Binary Search Tree is a linked structure of Nodes
• Each Node is an object
• Each node has a Key (and Data)
• Each Node has Left, Right, and Parent attributes which point to the Left Child, Right-Child, and Parent of the Node.
• If a child is missing then it is set to Nil.
• The root Node is the only Node with a Parent set to Nil.

When describing Binary Search Trees I'll tend to refer to the Nodes but mean the Nodes' keys (e.g. to say a Node is less than another means its key is less than the other Node's).

All the nodes in the left sub-tree of a node are less than or equal to the node and all the nodes in the right sub-tree of the node are greater than or equal to the node.

• Binary Search Tree Node
• Binary Search Tree Node Insertion
• Binary Search Tree: In-Order Traversal
• Binary Search Tree Queries
• Binary Search Tree: Randomized

• Introduction To Algorithms (CLRS)