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:

  1. Preorder
  2. Inorder
  3. Postorder
  4. 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:

  1. Visit D
  2. Output D
  3. Visit B
  4. Output B
  5. Visit A
  6. Output A
  7. Visit B
  8. Visit C
  9. Output C
  10. Visit B
  11. Visit D
  12. Visit E
  13. Output E
  14. Visit D
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

def preorder_traversal(node)
  # Perform some work on node
  p node.val
  
  # If the node has left child, recurse on the left subtree
  if node.left
    preorder_traversal(node.left)
  end
  
  # If the node has right child, recurse on the right subtree
  if node.right
    preorder_traversal(node.right)
  end
end

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.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

def inorder_traversal(node)
  if node.left
    inorder_traversal(node.left)
  end

  # Process the node
  p node.value
  
  if node.right
    inorder_traversal(node.right)
  end
end

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.

  1. Start at the root node and move to its left child B.
  2. Move that node’s left child A.
  3. Node A has no left or right child, so output the node A and return to the parent node B.
  4. The left child traversal is complete, move to the node’s right child C.
  5. Node C has no children, so output C and return to the parent node B.
  6. Node B’s left and right child visit is complete, output B. Return to the parent node D.
  7. Node D’s left child is visited, move to the right child E.
  8. Node E has no children, output E and return to teh parent node D.
  9. The node D’s left and right children traversal is now complete, output D.

The traversal order is A, C, B, E, D.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

def postorder_traversal(node)
  if node.left
    postorder_traversal(node.left)
  end
  if node.right
    postorder_traversal(node.right)
  end
  
  # Process the node
  p node.value
end

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.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

def height(node)
  if node.leaf?
    return 0
  else
    h = 0
    for child in node.children
      cheight = height(child)
      h = [h, cheight].max
    end
    # Add one for the edge between the current node
    # and the rest of the tree
    return 1 + h
  end
end

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.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

def breadth_first_traversal(root)
  # Create a queue to hold children for later processing
  children = []
  
  # Place the root node in the queue
  children << root
  
  # Process the queue until it becomes empty
  
  while !queue.empty?
    # Get the next node in the queue
    node = children.shift
    
    # Process the node
    p node.val
    
    # Add the node's children to the queue
    if node.left
      children << node.left
    end
    
    if node.right
      children << node.right
    end
  end
end

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.