A binary search tree is an ordered or sorted binary tree.
What’s a binary tree, you ask?
A binary tree is a node-based data structure where each node has at most two children.
A Left and right child node.
Still vague? Yes? How do we identify a binary search tree from other tree data structures?
Well, a BST has a few properties we can use for validation.
Properties of BST
- The node value at the left node is ALWAYS lesser than the current node’s value.
- The node value at the right node is ALWAYS greater than the current node’s value.
- The left and right nodes MUST be BSTs by satisfying the properties above.
That said, there are basic operations that can be performed on a BST:
Create— We can create an empty tree
Insert — We can insert nodes to a tree
Delete — We can delete nodes from a tree
Search — We can search for nodes in a tree
To search a BST, we will need to traverse the tree — we can traverse a tree in different orders.
Depth-first order — Traverses the tree nodes in-depth before moving to the next sibling. Pre-order, in-order and post-order traversals are different ways to traverse a tree in a depth-first approach.
Pre-order — Visits the current node, traverses the left subtree and then right subtree
In-order — Traverses the current node left subtree, then visits the current node and traverses the right subtree
Post-order — Traverses the current node left subtree, then traverses the current node right subtree, then visits the current node.
Breadth-first order — Traverses the tree in a level-order fashion. It traverses all nodes on the same level before going to the next level depth.
Let’s create a BST class.
See? It looks so simple. Next time, I’ll work through examples of inserting, deleting, and searching a BST.
