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.
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:
Post a Comment