Tree Traversal
excerpt: This article covers preorder, inorder and postorder traversal of binary trees. tags: tree-traversal
How to visit all the nodes of a tree? In a traversal, all the nodes are visited in some order and an operation is performed on them. The basic traversal enumerates the nodes so that you can see their ordering in the traversal. Searches are traversals where a particular node in a tree is searched. Any traversal can be used for a search.
Binary trees have four kinds of traversals:
- Preorder
- Inorder
- Postorder
- Breadth First
Preorder Traversal
In a preorder traversal, a node is processed and then its left child and then its right child. For example, consider the tree diagram. How can we display the tree’s nodes in a preorder traversal?
For preorder traversal of a tree, first visit the root node, this outputs the value D. Then move to the root node’s left child. Output B and move to that node’s left child. This outputs A. This node has no children, so the call returns to the previous node, B and visits that node’s right child.
The output is now C. This node has no children, so the call returns to the previous node, B. It has finished visiting that node’s children, so now the control moves up the tree again to node D and visits that node’s right child.
The output is now E. This node has no children, so control returns to the parent node, which is the root node. It has finished visiting that node’s children, so the traversal is now complete. The traversal order is D, B, A, C, E.
The program visits the nodes in one order but processes the nodes to produce an output in a different order. The steps taken to produce the output for preorder traversal:
- Visit D
- Output D
- Visit B
- Output B
- Visit A
- Output A
- Visit B
- Visit C
- Output C
- Visit B
- Visit D
- Visit E
- Output E
- Visit D
|
|
The method traverses the tree in preorder fashion. The current node is first processed. Instead of just printing the value, in a program you will peform some work specific to the problem in this line. This is the unit of work that is comman to all the recursive calls.
If the node has a left child, recursively traverse the left child’s subtree. Similarly we handle the right child if the node has a right child.
The main method can pass the root node to traverse the tree in preorder fashion. This method can be part of the node class. The root node can be encapsulated as an attribute of the node class, the parameter node for the method can be removed to simplify the interface.
The method can be modified slightly to extend the solution to trees with more than two children. The method will visit the node first and then visit its children.
Inorder Traversal
In an inorder traversal the processing order is left child, the node and then the right child. The traversal starts at the root node and moves to its left child B, then the traversal is from that node’s left child A. This node has no left child, so the output is A.
The node A has no right child, so control returns to the parent node B. The node B’s left child is finished, the output now is B. The control moves to that node’s right child C. Node C has no left child, so the node output is C. This node also has no right child, so the control returns to the parent node B. The node B’s right child is processed, so it returns to the root node D. The D’s left child is processed so it outputs D and then moves to its right child E.
Node E has no left child, so this node is visited and outputs E. The node also has no right child, so the control returns to the parent node D. The traversal order is A, B, C, D, e. This outputs the tree’s nodes in sorted order.
|
|
The method makes recursive call to the left child if it exists, processes the node and then makes a recursive call to the right child if it exists. The main method calls the inorder_traversal with the root node as the parameter to traverse the entire tree. It is not well defined how a tree with more than two children can be traversed in inorder fashion.
Postorder Traversal
In a postorder traversal the node’s left child is processed first, then its right child and finally the node.
- Start at the root node and move to its left child B.
- Move that node’s left child A.
- Node A has no left or right child, so output the node A and return to the parent node B.
- The left child traversal is complete, move to the node’s right child C.
- Node C has no children, so output C and return to the parent node B.
- Node B’s left and right child visit is complete, output B. Return to the parent node D.
- Node D’s left child is visited, move to the right child E.
- Node E has no children, output E and return to teh parent node D.
- The node D’s left and right children traversal is now complete, output D.
The traversal order is A, C, B, E, D.
|
|
The node’s left and right child is recursively processed if they exist. Then the node is processed. The main method can call this method with the root node as the parameter to traverse the entire tree. The postorder traversal for trees with more than two children can be defined. All the children of a node must be visited before visiting the node.
We can use post order traversal to find the height of an N-Ary Tree.
|
|
Breadth First Traversal
In a breadth first traversal, all the nodes at a given level of the tree is processed from left to right order before processing the nodes at the next level. For the tree in the diagram, the BFS starts at the root node’s level and outputs D. Then move to the next level and output B and E. The bottom level is processed last by outputting the nodes A and C. The complete traversal order is D, B, E, A, C.
A node’s children is added to a queue and they are processed after processing their parent’s level.
|
|
Create a queue and add the root node to it. The while loop processes every node in the tree by continuing to process until the queue is empty. Inside the while loop, the first node is removed from the queue, it is processed and its children are added to the queue.
A queue processes items in first in first out order, so all the nodes at a particular level in the tree are processed before any of their child nodes are processed.
The left child is added to the queue before adding the right node to the queue. So the nodes on a particular level are processed in left to right order.
The traversal visits all nodes once. So if a tree has N nodes, the run time is O(N). The recursive implementation uses stack that is equal to the tree’s height.
The space used by the breadth first traversal is highest when it is processing the last level which roughly holds half the total number of nodes, so if the tree holds N nodes, the queue holds O(N/2) = O(N) nodes.