Implement Inorder Traversal for Binary Search Tree in C++

This article will explain how to implement inorder traversal for binary search trees in C++.

Use Inorder Traversal to Print Contents of Binary Search Tree

A binary search tree is constructed so that each node’s key must be greater than all keys in its left subtree and less than all keys in the right subtree.

We only consider unbalanced trees here for the sake of simplicity, but in real-world scenarios efficiency of a binary search tree comes from the balanced nature, where each subtree of the root has roughly the same height.

Binary trees can be traversed using three different methods named: inorder, preorder, and postorder. Inorder traversal for the binary search tree yields the elements sorted in non-decreasing order. This version usually starts from the leftmost node and follows the order in which the left subtree will be traversed first, then the root node, and finally the right subtree.

Notice the following code snippet output and the order of the integers as they were inserted into a tree.

#include <iostream>
#include <vector>

using std::cout; using std::vector;
using std::endl; using std::string;

struct TreeNode {
    int key;
    struct TreeNode *left{};
    struct TreeNode *right{};
};

void insertNode(TreeNode *&root, const int k) {
    if (root == nullptr) {
        root = new TreeNode;
        root->key = k;
        root->left = nullptr;
        root->right = nullptr;
    } else {
        if (k < root->key)
            insertNode(root->left, k);
        else
            insertNode(root->right, k);
    }
}

void printTreeInorder(TreeNode *n) {
    if (n != nullptr) {
        printTreeInorder(n->left);
        cout << n->key << "; ";
        printTreeInorder(n->right);
    }
}

int main() {
    std::vector<int> v1 {11, 23, 3, 5, 9, 15, 2, 20};

    TreeNode *root = nullptr;

    for (const auto &item : v1) {
        insertNode(root, item);
    }

    printTreeInorder(root);
    cout << endl;

    return EXIT_SUCCESS;
}
2; 3; 5; 9; 11; 15; 20; 23;

Alternatively, we might need to utilize preorder or postorder traversal to access the node in the binary search tree. We only need to move cout << n->key << "; " line in printTree* functions to modify the traversal algorithm.

Preorder traversal starts printing from the root node and then goes into the left and right subtrees, respectively, while postorder traversal visits the root node in the end.

#include <iostream>
#include <vector>

using std::cout; using std::vector;
using std::endl; using std::string;

struct TreeNode {
    int key;
    struct TreeNode *left{};
    struct TreeNode *right{};
};

void insertNode(TreeNode *&root, const int k) {
    if (root == nullptr) {
        root = new TreeNode;
        root->key = k;
        root->left = nullptr;
        root->right = nullptr;
    } else {
        if (k < root->key)
            insertNode(root->left, k);
        else
            insertNode(root->right, k);
    }
}

void printTreePreorder(TreeNode *n) {
    if (n != nullptr) {
        cout << n->key << "; ";
        printTreePreorder(n->left);
        printTreePreorder(n->right);
    }
}

void printTreePostorder(TreeNode *n) {
    if (n != nullptr) {
        printTreePostorder(n->left);
        printTreePostorder(n->right);
        cout << n->key << "; ";
    }
}

int main() {
    std::vector<int> v1 {11, 23, 3, 5, 9, 15, 2, 20};

    TreeNode *root = nullptr;

    for (const auto &item : v1) {
        insertNode(root, item);
    }

    printTreePostorder(root);
    cout << endl;

    printTreePreorder(root);
    cout << endl;

    return EXIT_SUCCESS;
}
2; 9; 5; 3; 20; 15; 23; 11;
11; 3; 2; 5; 9; 23; 15; 20;
Contribute
DelftStack is a collective effort contributed by software geeks like you. If you like the article and would like to contribute to DelftStack by writing paid articles, you can check the write for us page.

Related Article - C++ Data Structure

  • Implement the Binary Tree Data Structure in C++
  • Binary Search Tree Insertion in C++