Tree Traversal and Binary Search Trees or BST

Hello, everybody! The topic for this week is Tree Traversals and Binary Search Trees or BST.

Tree Traversal is the process of visiting the individual nodes of a tree, with the objective of carrying out an operation or implementing a function at each.  There are essentially three ways to traverse a tree. The first is known as the in-order traversal, on which, a node is visited in between visiting its two children. The second is called the pre-order traversal and in this traversal, a node is visited before its children. Finally, the last method is the post-order traversal, and in this, a node is visited after visiting its children. Essentially, the different traversal methods, each give the programmer different powers and capabilities in carrying out operations or functions while tree traversal and thus, are useful in different situations.

 A BST is a special case of the Tree ADT, in which each root can have only a maximum of two children. Furthermore, in a Binary Search Tree, data is organized in such a way that for every root, its left child contains a value smaller than the value the root contains. Likewise, the root’s right child contains a value larger than the value the root contains. Therefore, data is essentially well-organised in a Binary Search Tree. Thus, it may be concluded that Binary Search Trees are extremely useful in sorting algorithms. Lastly, it should also be noted that pre-order traversal only makes sense in BSTs. Here is an example of a BST:

The problem I faced in this week’s lectures was in the BST insert and delete worksheet. I found it pretty hard to implement those methods because, tree traversal is still a bit unintuitive to me. I hope to get a better understanding of it in the labs.

That is all for this week, I hope everyone is having a great week. Please check out the linked blogs and leave a comment!http://2015-csc148.blogspot.ca/