What are Binary Search Trees?
Binary search trees are one of the fundamental data structures used in Computer Science.
The concept of binary search trees involves a collection of nodes. This includes one root node along with parents, children, and leaf nodes, all of the same type. Each node has either 0, 1, or 2 children nodes connected. The left child must be less than the parent and the right child must be greater than the parent. The nodes with no children are the leaf nodes. These inner collections of nodes make up what is called subtrees. This can form a tree-like structure visually.
10
/ \
8 15
/ \ / \
6 9 12 16
To create a binary search tree in Javascript we usually implement it through a class labeled something like BinarySearchTree or BST along with a Node class. We give our tree several methods such as insert(), remove(), and lookup().
class Node {
constructor(value) {
this.value = value;
this.left = null;
this.right = null;
}
}
class BinarySearchTree {
constructor(value) {
this.root = value;
}
lookup(node) {
...
}
insert(node) {
...
}
remove(node) {
...
}
}
To navigate these binary search trees we can do so through three main methods of traversal called inorder, preorder, and postorder. These are usually performed recursively in Javascript. Let’s go over these traversal methods in the following sections.
Inorder
To perform an inorder traversal we always traverse by starting at the left node first then visiting the current node and right node afterward.
inOrderTraverse(node) {
// check if tree node exists
if (node) {
// traverse down left subtree (Left, Node, Right)
inOrderTraverse(node.left);
console.log(node.value);
inOrderTraverse(node.right);
}
}
In this method, we’re first checking to make sure the current node is not null. Then if our node exists, we start our traversal. First, we recursively visit the left subtree, we then print out the current node, and finally, we recursively traverse the right subtree. This will be repeated until all nodes have been visited.
Preorder
For preorder traversal, we follow the same sort of steps just in a different order. We’re first going to start with the current node before moving on to the left and right nodes.
preOrderTraverse(node) {
if (node) {
// traverse tree preorder (Current, Left, Right)
console.log(node.value);
preOrderTraverse(node.left);
preOrderTraverse(node.right);
}
}
Like our inorder traversal, we check to make sure the current node we’re attempting to traverse exists. Then we visit the current node, printing it out before recursively calling our method on the left and right subtrees.
Postorder
The postorder traversal, as you may have guessed by now, does the opposite of preorder. First, we start by traversing the left child node before the right child node and lastly the current node.
postOrderTraverse(node) {
if (node) {
// traverse tree postorder (Left, Right, Current)
postOrderTraverse(node.left);
postOrderTraverse(node.right);
console.log(node.value);
}
}
Just like the previous traversal methods we always make sure to check that the node is not null. Then we recursively call our method on the left and right subtrees before printing the current node value until we have traversed the entire tree.
Summary
This was a brief explanation of some of the most common types of tree traversals in Computer Science. Each traversal technique gives us a different way to navigate and visit each node in a tree. For more on this subject check out the resources I’ve provided below.
Top comments (0)