Home | Projects | Notes > Data Structures & Algorithms > Tree Traversal (Pre-Order, In-Order, Post-Order)

Tree Traversal (Pre-Order, In-Order, Post-Order)

Tree Traversal

• Tree traversal refers to the process of systematically visiting and examining all the nodes (elements) of a tree data structure in a specific order. (Pre-Order, In-Order, Post-Order)

• It involves navigating through the nodes, which can be organized hierarchically, and performing actions on them as needed.

• Tree traversal is a fundamental operation for various algorithms and tasks involving trees, such as searching, sorting, and modifying data stored within the tree.

• Time Complexity of all 3 traversal algorithms: T = O(n), where 'n' is the number of nodes in the tree.

  • In ther worst case, where you have to visit every node of the tree, you visit each node exactly once.

• Space Complexity of all 3 traversal algorithms: : S = O(h), where 'h' is the height of the tree.

  • Each recursive call consumes space on the call stack. The maximum depth of the call stack is determined by the height of the tree.

  • In a balanced binary tree, the height is logarithmic in terms of the number of nodes (O(log n)), while in a skewed tree, it can be as bad as O(n).

Pre-Order Traversal (n-l-r): T = O(n), S = (h)

• Visits the current node first, then the left subtree, and finally the right subtree.

• Algorithm

  1. If the current node is null, return.

  2. Process the current node (print, store, etc.).

  3. Recursively perform a pre-order traversal on the left subtree.

  4. Recursively perform a pre-order traversal on the right subtree.

• Pseudo-code

  xxxxxxxxxx
  6
  1
  PreOrderTraversal(node):
  2
      if node is null:
  3
          return
  4
      Process(node)
  5
      PreOrderTraversal(node.left)
  6
      PreOrderTraversal(node.right)
  

In-Order Traversal (l-n-r): T = O(n), S = (h)

• Visits the left subtree, then the current node, and finally the right subtree.

• Algorithm

  1. If the current node is null, return.

  2. Recursively perform an in-order traversal on the left subtree.

  3. Process the current node (print, store, etc.).

  4. Recursively perform an in-order traversal on the right subtree.

• Pseudo-code

  xxxxxxxxxx
  6
  1
  InOrderTraversal(node):
  2
      if node is null:
  3
          return
  4
      InOrderTraversal(node.left)
  5
      Process(node)
  6
      InOrderTraversal(node.right)
  

Post-Order Traversal (l-r-n): T = O(n), S = (h)

• Visits the left subtree, then the right subtree, and finally the current node.

• Algorithm

  1. If the current node is null, return.

  2. Recursively perform a post-order traversal on the left subtree.

  3. Recursively perform a post-order traversal on the right subtree.

  4. Process the current node (print, store, etc.).

• Pseudo-code

  xxxxxxxxxx
  6
  1
  PostOrderTraversal(node):
  2
      if node is null:
  3
          return
  4
      InOrderTraversal(node.left)
  5
      Process(node)
  6
      InOrderTraversal(node.right)
  

   

Code (C++)

xxxxxxxxxx
78
1
#include <iostream>
2

3
using namespace std;
4

5
// Definition of a binary tree node
6
class TreeNode
7
{
8
public:
9
    int value;
10
    TreeNode *left;
11
    TreeNode *right;
12

13
    // Constructor
14
    TreeNode(int val) : value(val), left(nullptr), right(nullptr) { }
15
};
16

17
// Processes node
18
void processNode(TreeNode *node)
19
{
20
    cout << node->value << " ";
21
}
22

23
// Pre-Order Traversal
24
void preOrderTraversal(TreeNode *node)
25
{
26
    if (node == nullptr)
27
        return;
28

29
    processNode(node);
30
    preOrderTraversal(node->left);
31
    preOrderTraversal(node->right);
32
}
33

34
// In-Order Traversal
35
void inOrderTraversal(TreeNode *node)
36
{
37
    if (node == nullptr)
38
        return;
39

40
    inOrderTraversal(node->left);
41
    processNode(node);
42
    inOrderTraversal(node->right);
43
}
44

45
// Post-Order Traversal
46
void postOrderTraversal(TreeNode *node)
47
{
48
    if (node == nullptr)
49
        return;
50

51
    postOrderTraversal(node->left);
52
    postOrderTraversal(node->right);
53
    processNode(node);
54
}
55

56
int main(void)
57
{
58
    // Construct a sample binary tree
59
    TreeNode *root = new TreeNode(1);
60
    root->left = new TreeNode(2);
61
    root->right = new TreeNode(3);
62
    root->left->left = new TreeNode(4);
63
    root->left->right = new TreeNode(5);
64

65
    cout << "Pre-Order Traversal: ";
66
    preOrderTraversal(root);
67
    cout << endl;
68

69
    cout << "In-Order Traversal: ";
70
    inOrderTraversal(root);
71
    cout << endl;
72

73
    cout << "Post-Order Traversal: ";
74
    postOrderTraversal(root);
75
    cout << endl;
76

77
    return 0;
78
}

xxxxxxxxxx
3
1
Pre-Order Traversal: 1 2 4 5 3 
2
In-Order Traversal: 4 2 5 1 3 
3
Post-Order Traversal: 4 5 2 3 1