A Binary Search Tree is one of the various data structures that help us organize and sort data. It's an efficient way to store data in a hierarchy and is very flexible.
In this article, we will be taking a closer look at how it works—along with its properties and applications.
What Is a Binary Search Tree?
A Binary Search Tree is a data structure composed of nodes—similar to Linked Lists. There can be two types of nodes: a parent and a child. The root node is the beginning point of the structure branching off into two child nodes, called the left node and the right node.
Each node can only be referenced by its parent, and we can traverse the tree's nodes depending on the direction. The Binary Search Tree has three main properties:
- The left node is smaller than its parent.
- The right node is greater than its parent.
- The left and right subtrees must be Binary Search Trees.
A Perfect Binary Search Tree is achieved when all levels are filled, and every node has a left and right child node.
Basic Operations of a Binary Search Tree
Now you've got a better idea of what a Binary Search Tree is, we can look at its basic operations below.
1. Search Operation
Search allows us to locate a particular value present in the tree. We can use two types of searches: breadth-first search (BFS) and depth-first search (DFS). Breadth-first search is a searching algorithm that begins at the root node and traverses horizontally, side to-side, until the objective is found. Each node is visited once during this search.
Depth-first search, on the other hand, traverses the tree vertically—starting from the root node and working down a single branch. If the objective is found, the operation ends. But if not, it and searches the other nodes.
2. Insert Operation
The insert operation utilizes the search operation to determine the location where the new node should be inserted. The process starts from the root node, and the search begins until the destination is reached. There are three cases to consider with insertion.
- Case 1: When no node exists. The node to be inserted will become the root node.
- Case 2: There are no children. In this case, the node will be compared to the root node. If it is greater, it will become the right child; otherwise, it will become the left child.
- Case 3: When the root and its children are present. The new node will be compared to each node on its path to determine which node it visits next. If the node is greater than the root node, it will traverse down the right sub-tree or else the left. Similarly, comparisons are made on each level to determine whether it will go right or left until it arrives at its destination.
3. Delete Operation
The delete operation is used to remove a particular node within the tree. Deletion is considered tricky as after removing a node, the tree has to be re-organized accordingly. There are three main cases to consider:
- Case 1: Deleting a leaf node. A leaf node is a node without any children. This is the easiest to remove as it doesn't affect any other node; we simply traverse the tree until we reach it and delete it.
- Case 2: Deleting a node with one child. Deleting a parent with one node will result in the child taking its position, and all subsequent nodes will move up a level. There will be no change in the sub-trees structure.
- Case 3: Deleting a node with two children. When we have to remove a node with two children, we must first find a subsequent node that can take its position. Two nodes can replace the removed node, the inorder successor or predecessor. The inorder successor is the right subtree’s left-most child, and the inorder predecessor is the left subtree’s rightmost child. We copy the contents of the successor/predecessor to the node and delete the inorder successor/predecessor.
How to Traverse a Binary Search Tree
Traversal is the process through which we navigate a Binary Search Tree. It is done to locate a specific item or to print an outline of the tree. We always start from the root node and have to follow the edges to get to the other nodes. Each node should be considered a sub-tree, and the process is repeated until all nodes are visited.
- In-Order Traversal: Traversing in-order will produce a map in ascending order. With this method, we start from the left subtree and continue to the root and right subtree.
- Pre-Order Traversal: In this method, the root node is visited first, followed by the left subtree and the right subtree.
- Post-Order Traversal: This traversal involves visiting the root node last. We start from the left subtree, then the right subtree, and then the root node.
Real-World Applications
So, how do we utilize binary search tree algorithms? As it can be surmised, they are extremely efficient at searching and sorting. The greatest strength of binary trees is their organized structure. It allows searching to be done at remarkable speeds by cutting the amount of data we need to analyze by half per pass.
Binary Search Trees allow us to efficiently maintain a dynamically changing dataset in an organized form. For applications that have data inserted and removed frequently, they are very helpful. Video game engines use an algorithm based on trees known as binary space partition to help with rendering objects orderly. Microsoft Excel and most spreadsheet software use binary trees as their basic data structure.
You might be surprised to know that Morse code uses a binary search tree to encode data. Another prominent reason Binary Search Trees are so useful is their multiple variations. Their flexibility has led to numerous variants being created to solve all sorts of problems. When used properly, Binary Search Trees are a great asset.
Binary Search Trees: The Perfect Starting Point
One of the main ways to gauge an engineer's expertise is through their knowledge and application of data structures. Data structures are helpful and can help create a more efficient system. Binary Search Trees are a great introduction to data structures for any developer starting out.