Search This Blog

Friday, January 24, 2014

Difference between Depth First Search and Pre-Order Traversal

DFS is an algorithm to search a hierarchical structure. But, pre-order traversal seems to be something similar also. So, what is the difference between the two??



DFS says:
    •    If element found at root, return success.
    •    If root has no descendants, return failure
    •    Recursive DFS on left subtree: success if element found
    •    If not, Recursive DFS on right subtree: success if element found

Pre-order Traversal
    •    Visit the root
    •    Recursive pre-order on left subtree
    •    Recursive pre-order on right subtree

What are the differences then??
    •    DFS is a search i.e. it stops when it finds its target element. Pre-order traversal is a traversal and not a search i.e. it visits all the elements in the tree.

No comments:

My Profile

My photo
can be reached at 09916017317