Traversing a Binary Search Tree
This is the third blog post in a series on Binary Search Tree methods. In the last two blog posts, we discussed what a Binary Search Tree is briefly and then we went through the Inserting a Node method and a Contains Value method and how to optimally code both of these methods in Python. More recently, we discussed how to Remove a Node in Python. In this blog post, we are going to discuss the three main Binary Search Tree (BST) traversal methods: In Order Traverse, Pre Order Traverse, and Post Order Traverse. All of these traversals are implemented fairly similarly and are easy to code using Recursion.
First, let’s discuss and implement the In Order Traversal method. The In Order Traversal method is when you traverse the BST from the bottom of the left subtree, to the root, then to the right subtree. In the example tree above, an In Order Traversal would output an array that reads: [1, 3, 4, 6, 7, 8, 10, 13, 14]. To implement this in code, we will use Recursion and will basically traverse the left subtree by calling the traversal method, append the root value, and then traverse the right subtree by calling the traversal method. The code would look like the following:
Next, let’s look into the Pre Order Traversal method. The Pre Order Traversal method is when you traverse the BST from the root, then from the top of the left subtree, and then from the top of the right subtree. In the example tree above, a Pre Order Traversal would output an array that reads: [8, 3, 1, 6, 4, 7, 10, 14, 13]. Implementing this code is very similar to the In Order Traversal, the only change is that we are appending the root value to our array at the beginning in line 3, and then are running traversals on the left subtree and then the right subtree. The code looks like this:
Our last traversal method is Post Order Traversal. The Post Order Traversal method is when you traverse the BST from the bottom left of the left subtree, then traverse the right subtree, and then finally from the root. In the example tree above, a Post Order Traversal would output an array that reads: [1, 4, 7, 6, 3, 13, 14, 10, 8]. This method looks very similar to the previous two methods, except the array appends the current root value at the end of both traversals, which are ordered as the left subtree traversal and the then the right subtree traversal. The code would looks like this:
This was the third and final part of the Binary Search Tree Series. I hope that you enjoyed this article and the previous articles and have learned a lot about Binary Search Trees. Thank you for taking the time to read. Happy Coding!
