Nerd For Tech
Published in

Nerd For Tech

Tree Traversal

There are many ways to traverse a binary tree. The two most common ways to traverse a binary tree are depth-first search and breadth-first search.

Depth-First Search

Depth-first search works by starting at the root node and traversing as far as possible along the branches of the tree. Once the search reaches the end of a branch it will recursively go back and start searching the next branch. There are three types of traversal that depth-first search uses.

Inorder traversal goes in the order of left-root-right.

Example for printing out the numbers of the tree

You start at 12 because it is the root node for this tree. 12 is the root node so you will go to the left node which is 10.

10 two children so you will keep traversing to the left child 9.

9 has no children so it is going to be the first number printed. You will then go back to 10.

Now we will print 10 because it is the parent of the 9 and 11 nodes. You will then go to 11.

11 has no children and is the right node to 10 so it will be printed next. Now go back to 12 because all nodes to the left of 12 have been printed.

Now you will print the root node 12 and traverse to the right node which is 14.

14 has two children so you will go left to 13.

13 has no children so it will be printed. You will then go back to 14.

Now you will print 14 because it is the parent of 13. You will then go right to 15.

15 has no children so you will print 15. This is the last step as all nodes have been printed.

The next type of traversal is preorder traversal. Preorder is in the order root-left-right. The steps are similar to inorder except you will print the root first, then the left, and last the right. For the previous tree, the output of preorder tree traversal would be 12, 10, 9, 11, 14, 13, 15.

The last type is postorder traversal. Postorder is in the order left-right-root. You will print the left nodes, then the right nodes, and lastly the root nodes. For the previous tree, the output of postorder tree traversal would be 9, 11, 10, 13, 15, 14, 12.

Breadth-First Search

Breadth-first search is a traversal method that uses a queue to store the values of all the nodes on the current level before going down a level.

Example

Starting at the root we add 12 to the queue.

Now you will print 12 and move to the children of 12. You will add 10 and 14 to the queue.

Now print 10 and add all of 10’s children to the queue.

Now we print 14 and add 14’s children to the queue.

Now you will continue this pattern of printing the number at the top of the queue and adding its children to the back of the queue. In this case, there are no more children nodes so you will go through printing the queue until it is empty. You know you are done when the queue is empty and there are no more children left.

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store