Data Structures : Tree Traversals

(Week 2)

Tree traversals are one of the most important algorithm in computer science because sometimes we don't have linear data structure in that they are organized through in relationship or hierarchy. 

This allows us to traverse them in multiple ways. To clarify, tree traversal refers to the process of visiting each individual node exactly once. For our traversal, we will focus on binary trees, which are trees that have a max of two children. You can check out my earlier post on binary search trees. 

There are two types of traversal algorithm, Depth First and Breath First algorithms. Today, I am going to try to demonstrate Depth First Traversal which actually splits into 3 different algorithm. 

There are three types of depth-first traversal:

pre-order: visit the parent, then all the left children, and then all the right children. Pre-order traversal while duplicating nodes and values can make a complete duplicate of a binary tree. It can also be used to make a prefix expression (Polish notation) from expression trees: traverse the expression tree pre-orderly.

in-order: visit the left child, then the parent, and then the right child. This approach is useful for BSTs as it traverses the nodes in sorted order.  Also in-order traversal is very commonly used on binary search trees because it returns values from the underlying set in order, according to the comparator that set up the binary search tree (hence the name).

post-order: visit the left child, then the right child, and then the parent; however, post-order traversal while deleting or freeing nodes and values can delete or free an entire binary tree. It can also generate a postfix representation of a binary tree.

For depth-first traversal, we will require a stack data structure, which follows a Last In, First Out (LIFO) rule. For example ; You can think of a stack as a stack of newspapers; the newspaper on top was the last added to the pile, but the first to be grabbed by a customer for purchase. 

Lets see with example :  on Github

Data structure : Binary Search and Basic Duplicate Value Removal

(Week 1)

Data structure is one most important study in computer science, it facilitates many complex operations in software development.  As computer scientist, our job to perform operations on data such as getting input, processing that and outputting. These steps are happening everything we are surfing on the internet or making any transactions at an ATM machine. I would like to take this opportunity and demonstrate some of the basics in data structures. Today's example i would like to show how to apply binary search for very primitive search mechanism. Maybe we can also demonstrate duplicate values removal in a list. I m going to use python language so it might more convenient.

Binary search is one of the most common algorithm that many developers are using it. I also would like to talk about Big O notation and you may find more on Wikipedia. In computer science efficiency is the most important drive point. Most of the engineer and computer scientists are working on how to make a software or a system more efficient and cost-effective. Therefore data structure becomes high priority. Often engineers are trying to figure out the worse case scenario and that correlates with Time VS Data Size  which means efficiency.   So lets start with a small example :
You can also find this example on my github ...

How binary search work, here is the pseudo code :
1- get the length of the array
2- find the middle 
3- compare the given input if it is bigger , smaller or equal.
4- Don't forget Binary search is recursive algorithm so we need to call back our function inside of our function. and we need to keep going until it matches with our input.

	Data structure practice - 1
	Binary Search
	Duplicate removal in python lists
	data1 = [0, 1, 2,2, 8, 13,13, 17, 19, 32,32, 42]
	data2 = [0, 1, 24, 38, 113, 127, 19, 32, 42]
	finaldata = data1 + data2
	#Removes the duplicate values
	def remove_duplicates(test):
	mylist=[]
	seen = set()
	for x in test:
	if(x not in seen):
	mylist.append(x)
	seen.add(x)
	return mylist
	# gets user input
	def get_user_input(search):
	return search
	# if our input is empty or we only have a single subscript and that subscript is not the item that we are search for returns false
	def search_func(arr, item):
	if (len(arr) == 0 or len(arr) == 1 and arr[0] != item):
	return False
	mid = arr[len(arr)/2]
	if (item == mid):
	return True
	if(item < mid):
	return search_func(arr[:len(arr)/2],item)
	if(item > mid):
	return search_func(arr[len(arr)/2+1:],item)
	#main loop
	def main():
	filtered = remove_duplicates(finaldata)
	print('please enter a number : \n')
	search = input()
	target = get_user_input(search)
	traverse = search_func(filtered, target)
	print(traverse ,"Found ! \t", filtered)
	if __name__ == '__main__':
	main()