Binary search trees are a useful data structure for storing data in an ordered format that makes searching for values, insertion and deletion quick. Real-world applications include their use in search algorithms, 3D game engines and graphics. In this article, we will learn about a type of tree traversal algorithm called depth-first search that can be used to explore a binary search tree. We will learn how to implement the 3 types of depth-first search algorithms: pre-order, in-order and post-order using recursion. Tree traversal algorithms are a common subject in coding interview questions.
What is a Binary Search Tree?
A tree is a type of data structure. It is non-linear, which makes it a good data structure to store and search for data. Search time in a linear data structure, such as an array or linked list, increases proportionally as the size of the data set increases. A tree data structure splits up the data, decreasing the search time.
A tree data structure, unsurprisingly, looks like a tree when visualized. Normally it looks like an upside-down tree. It is made up of nodes that store data. The nodes are connected by edges, also known as branches. A parent node branch connects to a child node. The first node in the tree is known as the root node. It is positioned at the top of the upside-down tree. The root is connected to subtrees. A Subtree refers to all of the descendants (children, grandchildren, ...) of a node. At the ends of the branches, the nodes that have no children are referred to as leaves.
Trees are recursive data structures. What this means is that each node (that is not a leaf) is a parent of its children and each child is a parent of its children, whose children are parents of its children and so on. We will see, later in this article, that recursion can be used for the algorithms used to traverse trees. There are iterative solutions using while loops, but the simplest solutions are recursive.
A binary tree is a particular type of tree where each node has, at most, 2 children. A binary search tree is a type of binary tree that has ordered nodes. For any node in the binary search tree, the values of the nodes in all of the left child subtree nodes are less than the value of the parent node. The values of the nodes in all of the right child subtree nodes are greater than or equal to the value of the parent node. This affects the insertion order when the tree is created. This can be seen in the diagram below.
Why is a binary search tree useful?
Fast search, insert and delete
One measure of an algorithm's efficiency is its time complexity. It is an approximate measure of how long an algorithm takes to execute as the size of the data set, that the algorithm operates on, increases. The smaller the value, the better the algorithm. Time complexity is formally described using big O notation. You can think of the O as meaning "on the order of". It's a measure of the worst case for an algorithm. For example, a linear search algorithm (starts the search from the beginning of the data structure and checks each element sequentially) that searches for an element in a linked list or an array of size n will take ~O(n) steps. This is read as "big O of n" or "on the order of n". If there are 16 elements in the linear data structure, it will take 16 steps (worst case) to find the element using a linear search algorithm.
Binary search tree algorithms that search for an element in a binary search tree have a logarithmic run time, O(log n). This means that as the size of the data structure increases, the time taken for the operation increases logarithmically. This is much faster than a linear search. If there are 16 elements in a binary search tree. It will take O(log(16)) = 4 steps to find an element in a binary search tree. The logarithm is base 2. This difference becomes very pronounced as the data set size increases. If there are 1 048 576 elements. The linear search algorithm will take 1 048 576 steps to find an element in the worst case. The binary search tree algorithm will take 20 steps in the worst case.
Insertion and deletion are also quick in a binary search tree. When data is inserted, it is stored by reference. This means that a new piece of memory is created when it is a node is added to a binary search tree and it points to the parent node that it is connected to. The nodes can be spread out in memory. If you were to insert or delete an element from the middle of an array, many operations would need to be performed to shift the values in the array. This is because values in an array are all next to each other in memory.
Why is the search time in a binary search tree logarithmic?
A logarithm is defined as the inverse function to exponentiation. What this means is that if you have a logarithm, say log2(16). You can get the answer by asking: "What power do I have to raise 2 to get an answer of 16?". This can be written as 2? = 16. Divide and conquer algorithms that continually divide a data structure in half are logarithmic (base 2). This includes binary search tree algorithms. Logarithms that are base 2 can be considered as divisions by 2.
log2(16) = 4 can be read as: "I have to raise 2 to the power of 4 to get an answer of 16". This is equivalent to: "16 requires 4 divisions by 2 to reach a value of 1".
16 / 2 = 8 -> 8 / 2 = 4 -> 4 / 2 = 2 -> 2 /2 = 1.
For example, if you have 16 elements in a binary search tree, like in the image below, the time complexity is O(log n). This means it will take O(log(16)) or 4 steps, in the worst case, to find an element. This is equal to the height of the tree. When searching for an item, starting at the root, the correct direction, left or right, can be chosen at each step because the nodes are ordered. At each step, the number of nodes to search is halved. The problem size is halved with each step.
The binary search trees used in this article are balanced. This means that the nodes are spread out well. The height of a tree is the number of nodes between the root node and a leaf node. A tree may have many different heights. If the difference between the maximum height and minimum height is 1 or 0, then the tree is balanced.
Logarithmic search times occur for balanced trees. The more unbalanced a binary search tree becomes, the slower the search time. The search time becomes more linear as the tree starts to become more linear (O(n)). There are self-balancing trees that can be used for dynamic data sets. This is beyond the scope of this article - you can read more about them in this Wikipedia article: Self-balancing binary search tree.
Exploring a binary search tree: Depth-first search
Various algorithms allow you to visit each node in a tree instead of searching for a specific value. These algorithms are used to explore the data: each node's value is read and can be checked or updated. They can be broadly divided into depth-first and breadth-first search.
Breadth-first, also known as level-order, search algorithms read the value of all the nodes at a particular level in a tree before moving on to the next level. The progression of the algorithm as it traverses the tree and reads the node values is breadth-first. It starts at the root node and moves down the tree level by level.
Depth-first search algorithms first read all of the node values in a particular subtree. The subtree is traversed deeply, all the way to the bottom leaves, before moving on to the next subtree. We will explore depth-first search algorithms in more detail.
There are 3 types of depth-first search: pre-order, in-order and post-order. In these algorithms, the root, the left subtree of the root and the right subtree of the root are traversed. The difference between them is the order in which the node values are read:
- pre-order: root -> left subtree -> right subtree
- in-order: left subtree -> root -> right subtree
- post-order: left subtree -> right subtree -> root
In pre-order search, the root value is read first and then the subtree values are read. In in-order search, the first node read is the left-most node in the BST. The last node read is the right-most node in the BST. In post-order search, the leaves are read first and then the roots are read.
Let's explore how this traversal occurs through each node. The following CodePen shows the three types of depth-first search tree traversal algorithms. Click on the buttons to visualize the traversal and see the order in which the nodes are visited and read. Notice that in-order traversal prints the values of the nodes in order.
Implement depth-first search in JavaScript
Let's implement the 3 types of depth-first search algorithms. The inspiration for writing this article came from doing a freeCodeCamp challenge on using depth-first search in a binary search tree. You can try the challenge before continuing.
The implementations used here make use of recursive functions. This means that the functions call themselves. The recursion stops when the base case is reached. In the depth-first search algorithms implemented here, the root node is passed in as an argument to the recursive algorithm function. Its left child or right child is recursively passed in as an argument to the same function. The left and right children are subtrees of the parent node. The recursion stops when the left node and the right node of the node being traversed is null. In other words, when a node with no children, a leaf, is reached. During the recursion, the value of the current node is added to an array. The output of the algorithms is an array of the visited nodes. The order of the array elements is equal to the order in which the nodes were read.
The code below will be used as a base for implementing the algorithms. We will implement the algorithms as methods within a BinarySearchTree function. There is an add method that will be used to add nodes to the tree when we test the algorithm. The Node function is used by the add method to create nodes. There is also a displayTree function that will be used to visualize the tree, as a string, in the console. For simplicity, no duplicate values will be allowed in the binary search tree. From now on, binary search tree will be abbreviated as BST.
// converts created binary search tree into a JSON string
// JSON.stringify(value, replacer, space)
// tree will be the passed in BST
// null means that all properties are included in the JSON string
// 2 adds some white space to the JSON string output to make it more readable
var displayTree = tree => console.log(JSON.stringify(tree, null, 2));
function Node(value) {
// give node a value
this.value = value;
// node has no children initially
this.left = null;
this.right = null;
}
function BinarySearchTree() {
// root is initially empty - no nodes
this.root = null;
// add node to tree
// value and current node (currNode) passed in as arguments
// the default value of currNode is this.root
this.add = (value, currNode = this.root) => {
// create a new node
let newNode = new Node(value);
// if no nodes in tree, make newly added node the root
if(!this.root) {
this.root = newNode;
} else {
// no duplicate values allowed - for simplicity
if (value === currNode.value) {
return null;
// add node to left subtree
} else if (value < currNode.value) {
// if no left child, add new node as left child - base case
// else recursively call add() again - currNode changes - moving down tree
!currNode.left ? currNode.left = newNode : this.add(value, currNode.left);
// add node to right subtree
} else {
!currNode.right ? currNode.right = newNode : this.add(value, currNode.right);
}
}
}
}
The 3 algorithms for pre-order, in-order and post-order are very similar. They will be added as methods to BinarySearchTree. They all share the following code:
this.method = () => {
if (this.root === null) {
return null;
} else {
let values = [];
function traversefunction(currNode) {
// different for each method
}
traversefunction(this.root);
return values;
}
}
The first thing we check is if the root is null, which would mean the BST has no nodes. If this is the case we return null as there is no BST to traverse. The output of the method is stored in the value array and is returned from the function.
Each method has a traverse function used to traverse the tree. It is initially called with the root node as an argument. These traversal functions are recursively called to traverse the BST tree. These traversal functions are where the methods differ. The traversal functions differ in the order of execution of the current node value being pushed into the array.
// PRE-ORDER
// add current node value
values.push(currNode.value);
// if left child node exists - traverse left subtree
currNode.left && traversePreOrder(currNode.left);
// if right child node exists - traverse right subtree
currNode.right && traversePreOrder(currNode.right);
// IN-ORDER
// if left child node exists - traverse left subtree
currNode.left && traversePreOrder(currNode.left);
// add current node value
values.push(currNode.value);
// if right child node exists - traverse right subtree
currNode.right && traversePreOrder(currNode.right);
// POST-ORDER
// if left child node exists - traverse left subtree
currNode.left && traversePreOrder(currNode.left);
// if right child node exists - traverse right subtree
currNode.right && traversePreOrder(currNode.right);
// add current node value
values.push(currNode.value);
Before we continue with explaining each method in detail, let's briefly learn about the call stack so that we can better understand the recursive function calls in the algorithms.
What is the call stack?
A call stack is a mechanism used by the JavaScript Engine interpreter to keep track of function calls. The JavaScript engine is the program that reads, interprets, optimizes and executes JavaScript code. It converts human-readable JavaScript code into machine-readable code. When a function is called, the JavaScript Engine interpreter adds it to the top of the call stack and starts executing the function. If the function calls another function, which may be the same function (recursive function call), the newly called function is added to the top of the call stack. The call stack uses the last-in-first-out (LIFO) principle. When the current function, which is at the top of the call stack, completes its execution it is popped off the call stack. A functions execution is complete when it returns a value or reaches the end of its scope. The interpreter then resumes execution of the code from where it left off on the call stack, which is the function that is now at the top of the call stack. The GIF below shows an example of how function calls are added and removed from the call stack. This example does not show, for simplicity, the execution of the main function, which is the execution of the whole script. You can read more about the call stack in this article: JavaScript Event Loop And Call Stack Explained.
Pre-order
Let's Implement the preOrder method. In your code editor or your browser dev tools add the displayTree, Node and BinarySearchTree functions from the code above. Add the preorder method, displayed in the code below, to the BinarySearchTree function:
this.preOrder = () => {
if (this.root === null) {
return null;
} else {
let values = [];
function traversePreOrder(currNode) {
values.push(currNode.value); // add current node (subtree root)
currNode.left && traversePreOrder(currNode.left); // traverse left subtree
currNode.right && traversePreOrder(currNode.right); // traverse right subtree
}
traversePreOrder(this.root);
return values;
}
}
At the bottom of the script, add the code displayed below. We create a new BST called testBST, it is an instance of the BinarySearchTree object that contains the preOrder and add method. Then we add nodes to it using the add method. The BST has the same nodes as the interactive CodePen BST shown earlier.
We then console log the the created BST to visualize it using the displayTree function and then console log the preorder method to see its output.
var testBST = new BinarySearchTree();
testBST.add(5);
testBST.add(3);
testBST.add(2);
testBST.add(4);
testBST.add(8);
testBST.add(6);
testBST.add(9);
console.log('Binary search tree: ',JSON.stringify(testBST.root, null, 2));
console.log('Binary search tree: pre-order search ', testBST.preOrder());
The output of the console logs should be:
binary search tree: {
"value": 5,
"left": {
"value": 3,
"left": {
"value": 2,
"left": null,
"right": null
},
"right": {
"value": 4,
"left": null,
"right": null
}
},
"right": {
"value": 8,
"left": {
"value": 6,
"left": null,
"right": null
},
"right": {
"value": 9,
"left": null,
"right": null
}
}
}
Binary search tree: pre-order search Array(7) [ 5, 3, 2, 4, 8, 6, 9 ]
You can compare the console logged BST JSON string to the BST in the CodePen example, the trees are the same. The output of the pre-order search also matches the output of the pre-order search in the CodePen example.
Now let's go through the execution of the function calls step by step to understand the traversal, order of the recursive function calls and the order in which the values are read and added to the values array. The following slide show shows how the traversePreOrder function within the preOrder method is recursively called. It shows how the recursively called traversePreOrder function is added to and removed from the call stack during the execution of the preOrder method. The BST traversal is visually shown in the middle. The addition of node values to the values array is shown at the bottom left. Note that the stack continues to grow until a leaf node is reached, the maximum stack height occurs when a leaf is reached. The maximum stack height of the traversePreOrder functions (ignoring the preOrder function on the stack) is 3, which is equal to the height of the BST. The space complexity of the tree is O(h), where h is the height of the tree. We learnt earlier that an algorithm's time complexity is an approximate measure of how long an algorithm takes to execute as the size of the data set, that the algorithm operates on, increases. An algorithm's space complexity is an approximate measure of how much memory is needed to execute the algorithm as the size of the data set increases.
In-order
Let's Implement the inOrder method. In the code you used for the preOrder method, add the following inOrder method to the BinarySearchTree function:
this.inOrder = () => {
if (this.root === null) {
return null;
} else {
let values = [];
function traverseInOrder(currNode) {
currNode.left && traverseInOrder(currNode.left);
values.push(currNode.value);
currNode.right && traverseInOrder(currNode.right);
}
traverseInOrder(this.root);
return values;
}
}
Add the following console log at the end of the script to test the method:
console.log('Binary search tree: in-order search ', testBST.inOrder());
The output of the added console log should be:
Binary search tree: in-order search Array(7) [ 2, 3, 4, 5, 6, 8, 9 ]
Now let's go through the execution of the function calls step by step to understand the algorithm. The following slide show shows how the traverseInOrder function is recursively called. If you compare the call stack execution to the traversePreOrder function in the previous section, you will notice that the order of recursive function calls is the same. The point at which the current node value is pushed into the values array differs. This is the same for the traversePostOrder method that will be described in the next section.
Post-order
Let's Implement the last method, the postOrder method. Add the following. Add the following postOrder method to the BinarySearchTree function:
this.postOrder = () => {
if (this.root === null) {
return null;
} else {
let values = [];
function traversePostOrder(currNode) {
currNode.left && traversePostOrder(currNode.left);
currNode.right && traversePostOrder(currNode.right);
values.push(currNode.value);
}
traversePostOrder(this.root);
return values;
}
}
Add the following console log at the end of the script to test the method:
console.log('Binary search tree: post-order search ', testBST.postOrder());
The output of the added console log should be:
Binary search tree: post-order search Array(7) [ 2, 4, 3, 6, 9, 8, 5 ]
Now let's go through the execution of the function calls step by step to understand the algorithm. The following slide show shows how the traversePostOrder function is recursively called.
Conclusion
Binary search trees are a useful data structure that can be explored using depth-first search algorithms. The 3 types of depth-first search algorithms: pre-order, in-order and post-order can be implemented using recursion. They are very similar algorithms, they only differ in the order in which the node values are read. Understanding these algorithms can help you pass your next coding interview and you may even find yourself using them in a real-world application.
Here are some useful links for further study:
1) freeCodeCamp Coding Interview Prep - Data Structures
2) JavaScript Event Loop And Call Stack Explained
3) Python tutor: Visualize execution of code (Python, Java, C, C++, JavaScript, or Ruby) - line by line
Top comments (1)
Thanks for that!! It was very fun, i learned a lot!