My Binary Search Tree Traversal Cheat - Cebu X-Geeks


Monday, June 16, 2014

My Binary Search Tree Traversal Cheat

Back in college, I have this “odd” way of illustrating Binary Search Trees. Instead of using a circle (it’s what my professor draws) to represent an element or a node, I use a right triangle.

Example, given this set of numbers 50, 25, 100, 75, 83, 61, 25, 15, and 10, the diagram below represents how my professor (as well as books) would illustrate it. The second diagram shows how I do it.
How I do it.

How my professor and books illustrates it.
I’m not certain if I’m the only one who does it this way. But I just want to share this here as someone might find this helpful.

The reason why I illustrate a binary search tree in such format is so that I can answer the traversal questions easily. I strongly believe that having a strong understanding of this Data Structure basic is important for computer science majors. However, it doesn’t hurt if you embrace tricks to make your student life easier. And to better understand how this cheat works, let us do a quick review.

What is a Binary search Tree (BST)?

"It is a binary tree in which all elements in the left subtree of a node is less than the content of the node, and all elements at the right subtree are greater than or equal to the content of the node. BSTs are mostly implemented for search and sort operations."

To learn more about binary trees in general, check out this link.

There are several traversal strategies or ways of visiting the nodes in a tree, the most common methods includes: pre-order, post-order, and in-order. You can find their corresponding algorithms below.

Pre-order Traversal

a. Visit the root
b. Traverse the left sub-tree in pre-order
c. Traverse the right sub-tree in pre-order

Post-order Traversal

a. Traverse the left sub-tree in post-order
b. Traverse the right sub-tree in post-order
c. Visit the root

In-order Traversal

a. Traverse the left sub-tree in in-order
b. Visit the root
c. Traverse the right subtree in in-order

At first glance, you can’t easily understand the above steps unless otherwise you are a computer science genius or something similar. I must admit, I wasn’t the brightest in my class and it took me quite some time to grasp them. And for this reason, I’ve come up with this trick to help me pass this subject.

Again, instead of using a circle to represent nodes, use a right triangle. Actually, any triangle will do but for the sake of consistency let’s just use the right triangle.
Imagine this is a node.
If you need to get the pre-order sequence of the elements in a binary search tree, the vertical lines serves as your guide. For post-order traversal, the diagonal lines. While the horizontal lines when doing in-order.

The traversal cheat diagram

Pre-order: 50, 25, 15, 19, 25, 100, 75, 61, 83

Post-order: 10, 15, 25, 25, 61, 83, 75, 100, 50

In-order: 10, 15, 25, 25, 50, 61, 75, 83, 100

Ok, so now you might get away with theory exams. However, the application part is a whole different story.

If you think this idea is stupid or brilliant, feel free to post in the comments section below.

No comments:

Post a Comment