#DOTD: Tree Traversal

1 Oct 2017

Traversing, or searching, a tree involves visiting each node of the tree exactly once.

 

Depth-First Search (DFS) involves going as deep as possible in a subtree before moving on to the next, whereas in Breadth-First Search (BFS), each level is completed before moving to the next. Monte Carlo Tree Search (MCTS) is neither DFS or BFS + used in artificial intelligence.

 

There are three types of DFS:

1. Pre-order traversal begins at the root, traverses the left sub-tree, then traverses the right sub-tree.

2. Post-order traversal begins with traversal of the left sub-tree, then the right sub-tree + ends at the root. 

3. In-order traversal begins with traversal of the left sub-tree, reaches the root + ends with traversal of the right sub-tree.

 

The following video is a great resource for learning DFS:

 

 

 

 

 

 

 

Share on Facebook
Share on Twitter
Share on LinkedIn
Please reload

Please reload

Related Posts
PhDomics by Fatima