Tree Traversal – inorder, preorder, and postorder (With Code in C++/Python/Java)

Tree traversal is the process of visiting (checking and/or updating) each node in a tree data structure, exactly once, in a specific order.

There are three common ways to traverse a tree:

• In-order traversal
• pre-order traversal
• post-order traversal

In-order traversal

In-order traversal visits the nodes of a tree in the following order: left subtree, root, right subtree.

Algorithm

Here is the algorithm for in-order traversal:

1. Traverse the left subtree by calling the in-order function on the root of the left subtree.
2. Visit the root node.
3. Traverse the right subtree by calling the in-order function on the root of the right subtree.

Example

Here is an example of in-order traversal on the following tree:

       1
     /   \
    2     3
   / \   / \
  4   5 6   7

The in-order traversal would visit the nodes in the following order: 4, 2, 5, 1, 6, 3, 7.

Code

Here is some example code for in-order traversal in Python:

def in_order_traversal(node):
  if node is not None:
    in_order_traversal(node.left)
    print(node.value)
    in_order_traversal(node.right)

Here is some example code for in-order traversal in C++:

void in_order_traversal(Node *node) {
  if (node != nullptr) {
    in_order_traversal(node->left);
    cout << node->value << " ";
    in_order_traversal(node->right);
  }
}

Here is some example code for in-order traversal in Java:

public static void inOrderTraversal(Node node) {
  if (node != null) {
    inOrderTraversal(node.left);
    System.out.print(node.value + " ");
    inOrderTraversal(node.right);
  }
}

Pre-order traversal

Pre-order traversal visits the nodes of a tree in the following order: root, left subtree, and right subtree.

Algorithm

Here is the algorithm for in-order traversal:

1. Traverse the left subtree by calling the in-order function on the root of the left subtree.
2. Visit the root node.
3. Traverse the right subtree by calling the in-order function on the root of the right subtree.

Example

Here is an example of in-order traversal on the following tree:

       1
     /   \
    2     3
   / \   / \
  4   5 6   7

The pre-order traversal would visit the nodes in the following order: 1, 2, 4, 5, 3, 6, 7.

Code

Here is some example code for pre-order traversal in Python:

def pre_order_traversal(node):
  if node is not None:
    print(node.value)
    pre_order_traversal(node.left)
    pre_order_traversal(node.right)

Here is some example code for pre-order traversal in C++:

void pre_order_traversal(Node *node) {
  if (node != nullptr) {
    cout << node->value << " ";
    pre_order_traversal(node->left);
    pre_order_traversal(node->right);
  }
}

Here is some example code for pre-order traversal in Java:

public static void preOrderTraversal(Node node) {
  if (node != null) {
    System.out.print(node.value + " ");
    preOrderTraversal(node.left);
    preOrderTraversal(node.right);
  }
}

Post-order traversal

Post-order traversal visits the nodes of a tree in the following order: left subtree, right subtree, root.

Algorithm

Here is the algorithm for post-order traversal:

1. Traverse the left subtree by calling the post-order function on the root of the left subtree.
2. Traverse the right subtree by calling the post-order function on the root of the right subtree.
3. Visit the root node.

Example

Here is an example of post-order traversal on the following tree:

       1
     /   \
    2     3
   / \   / \
  4   5 6   7

The post-order traversal would visit the nodes in the following order: 4, 5, 2, 6, 7, 3, 1.

Code

Here is some example code for post-order traversal in Python:

def post_order_traversal(node):
  if node is not None:
    post_order_traversal(node.left)
    post_order_traversal(node.right)
    print(node.value)

Here is some example code for post-order traversal in C++:

void post_order_traversal(Node *node) {
  if (node != nullptr) {
    post_order_traversal(node->left);
    post_order_traversal(node->right);
    cout << node->value << " ";
  }
}

Here is some example code for post-order traversal in Java:

public static void postOrderTraversal(Node node) {
  if (node != null) {
    postOrderTraversal(node.left);
    postOrderTraversal(node.right);
    System.out.print(node.value + " ");
  }
}