What is a Binary Search Tree?

Binary Search Trees are a hierarchical, node-based structure whose sorted nature makes for efficient search, deletion, and insertion operations.

How can I use a Binary Search Tree?

• Red-Black Trees: an example of a self-balancing BST that maintains balance by coloring nodes black and red during insertion and deletion operations, always having O(log n) time!
• AVL Trees: a self-balancing BST that rotates when the difference between the height of any two subtrees is at least |2|.
• Ordered Data Management: the structure of a BST ensures that all nodes are in sorted order, which makes it great for databases and sorted lists, as all elements are in sorted order.

Beyond the project we do in class, one use of the Binary Search Tree is the simplification of Morse Code.

In the above image, a Binary Tree shows how a Binary Search Tree can be used to decode a string of dots and dashes, simplifying Morse Code such that we don't need to memorize every possible letter.

To learn more about BSTs, click here!