JIYIK CN >

A binary tree is a non-linear data structure. It is called a binary tree because each node has at most two children. These children are called left and right children. It can also be interpreted as an undirected graph where the topmost node is called the root. Unlike linear data structures that can be traversed in only one way, a tree can be traversed in different ways. We can traverse a tree by exploring along the depth or the breadth. The first method is called depth-first traversal and the second method is called breadth-first traversal. In this article, we will discuss depth-first traversal.

There are 3 types of depth-first traversal - in-order traversal, pre-order traversal and post-order traversal. We will discuss them one by one.

Binary Tree Traversal

In-order traversal

In this traversal, we first visit the left subtree, then the root, and finally the right subtree. Each node is similar to a subtree. For BST, in-order traversal returns all elements in ascending order.

Pre-order traversal

In this traversal, we first visit the root, then the left subtree and finally the right subtree. Each node resembles a subtree. It is often used for replication, i.e. creating a copy of the tree. Prefix traversal also helps in generating prefix expressions from expression trees.

Post-order traversal

In this traversal, we first visit the left subtree, then the right subtree and finally the root. Each node is similar to a subtree. It is used to delete the tree efficiently. It also helps in generating suffix expressions from expression trees.

Binary tree traversal diagram

In-order traversal:(4、2、1、5、3、6、7、8、9)

We 3call an in-order traversal on the root node . Recursively traverse leftward to reach the node 4, which is the leftmost node and include it in our output; since it is the root node and has no left node, we visit its rightmost node 2and include it in our traversal. In this way, we traverse the entire tree and get the above order as our output.

Pre-order traversal:(3，1，4，2，5，7，6，9，8)

We 3call a pre-order traversal on the root node and include it in our output. We then recursively traverse left to the next root node 1, followed by 4. Since 4has no left child, we visit the node to the right 2. Now that we have covered 4the subtree under the root node , we backtrack to the node 1and walk right to the node 5. In this way, we traverse the entire tree and get the above order as our output.

Post-order traversal:(2，4，5，1，6，8，9，7，3)

We 3call post-order traversal on the root node , recursively traversing left to reach the node 4. Before 4we include in our traversal, we must visit its right node 2. 1's right node 5is not visited, so we 5include first, and then 1output . We then trace back to the root node 3, and continue traversing the right subtree. In this way, we traverse the entire tree and get the above order as our output.

Binary Tree Traversal Algorithm

In-order traversal

• Traverse the left subtree by recursively calling the in-order function.
• Visit the root node.
• The right subtree is traversed by recursively calling the in-order function.

Pre-order traversal

• Visit the root node.
• Traverse the left subtree by recursively calling the in-order function.
• Traverse the right subtree by recursively calling the sequential inner function.

Post-order traversal

• Traverse the left subtree by recursively calling the in-order function.
• The right subtree is traversed by recursively calling the in-order function.
• Visit the root node.

Implementation of binary tree traversal

#include <iostream>
using namespace std;

class Node {
public:
    int key;
    Node *left, *right;
    Node(int x) {
        this->key = x;
        this->left = this->right = NULL;
    }
};

void inorder(Node *root) {
    if (root != NULL)
    {
        inorder(root->left);
        cout << root->key << " ";
        inorder(root->right);
    }
}
void preorder(Node*root) {
    if (root != NULL) {
        cout << root->key << " ";
        preorder(root->left);
        preorder(root->right);
    }
}

void postorder(Node* root) {
    if (root != NULL) {
        postorder(root->left);
        postorder(root->right);
        cout << root->key << " ";
    }
}

int main() {
    Node* root = new Node(3);
    root->left = new Node(1);
    root->right = new Node(7);
    root->left->left = new Node(4);
    root->left->right = new Node(5);
    root->left->left->right = new Node(2);
    root->right->left = new Node(6);
    root->right->right = new Node(9);
    root->right->right->left = new Node(8);
    cout << "The inorder traversal of the tree is : "; inorder(root); cout << endl;
    cout << "The preorder traversal of the tree is : "; preorder(root); cout << endl;
    cout << "The postorder traversal of the tree is : "; postorder(root); cout << endl;
}

Complexity of binary tree traversal algorithm

Time Complexity

• Average situation

nThere are nodes in a tree . 3In all traversals, we must visit each node. Since we niterate over nodes, although the order is different, the time complexity of the three traversals is O(n). The time complexity in the average case is O(n).

• Best Case

The best case time complexity is O(n). It 3is the same as the average case time complexity of all traversals.

• Worst case scenario

The worst case time complexity is O(n). It 3is the same as the worst case time complexity of all traversals.

Space complexity

Due to the additional space required for the recursive calls, the space complexity of this algorithm is O(n).