# TreeTraversal Algorithms

Common ways for traversing a binary tree

Tree traversal is a form of graph traversal, its the process of visiting each node in a data structure in order to retrieve data. Tree traversal algorithms are classified by the order in which the nodes are visited, here ill go over Preorder traversal, Inorder traversal, Postorder traversal, level order traversal.

Preorder traversal begins by visiting the root of the tree and then recursively processing all the subtrees by first traversing the left tree and then traversing the right tree.

In the above image, if we were to use preorder traversal we would begin at node 1, move left to node 2, again move left to node 4, and then again move left to node 8. now that we are at a node that no longer points to another node on the left, we move back up to node 4 and then traverse right to node 9. the left subtree will always be visited first until completely visited, then it will return to the nearest value that has a right tree that has yet to be visited. when we eventually reach the root node again, node 1, we will pass down to the right side and process the right tree again, still moving left before right. Let it be noted that each time we move to a different node we will collect the output of the node.

In-order tree traversal begins by traversing left, then visiting a node, then traversing right.

In this example, we will begin at node F and then move down to node b, since we are using in-order traversal we will not collect the output of node B. we now move down to node A, since there is no longer a left subtree of A we will record the output of node A. since there is no right subtree we will move back up to Node B. Since there is no longer a left subtree that has not been traversed, we will collect the output of B and traverse the right subtree. this pattern is followed in the right subtree of node B, going from Node D to Node C, collecting the output, then returning to D, collecting the output then going down the right tree.

Postorder tree traversal follows the three steps of traversing left, traversing right, then visiting the node.

using the same node tree. beginning at node F, we traverse to Node B, then traverse to node A. we then try to traverse left and right. since there are no subtrees to traverse we move back up to Node B collecting node A’s output, and traverse to the right subtree node D. from D we traverse left to node C, then as there are no subtrees, we collect node C’s output and then we traverse back to D and then move to E. from here we traverse back to node D, and B, collecting their outputs along the way. data collected in this tree would go in order node[A, C, E, D, B, H, I, G, F]