Traversal (Inorder traversal of BST)

In case of binary search trees (BST), Inorder traversal gives nodes in non-decreasing order. We visit the left child first, then the root, and then the right child.

Below is the implementation of how to do inorder traversal of a Binary Search Tree:

C++

// C++ program to implement
// inorder traversal of BST
#include <bits/stdc++.h>
using namespace std;

// Given Node node
struct node
{
    int key;
    struct node *left, *right;
};

// Function to create a new BST node
struct node* newNode(int item)
{
    struct node* temp = (struct node*)malloc(
            sizeof(struct node));
    temp->key = item;
    temp->left = temp->right = NULL;
    return temp;
}

// Function to insert a new node with
// given key in BST
struct node* insert(struct node* node, int key)
{
    
    // If the tree is empty, return a new node
    if (node == NULL)
        return newNode(key);

    // Otherwise, recur down the tree
    if (key < node->key) 
    {
        node->left = insert(node->left, key);
    }
    else if (key > node->key)
    {
        node->right = insert(node->right, key);
    }

    // Return the node pointer
    return node;
}

// Function to do inorder traversal of BST
void inorder(struct node* root)
{
    if (root != NULL) 
    {
        inorder(root->left);
        cout << " " << root->key;
        inorder(root->right);
    }
}

// Driver Code
int main()
{
    
    /* Let us create following BST 
              50 
           /     \ 
          30      70 
         /  \    /  \ 
       20   40  60   80 
   */
    struct node* root = NULL;

    // Creating the BST
    root = insert(root, 50);
    insert(root, 30);
    insert(root, 20);
    insert(root, 40);
    insert(root, 70);
    insert(root, 60);
    insert(root, 80);

    // Function Call
    inorder(root);

    return 0;
}

// This code is contributed by shivanisinghss2110

// C program to implement
// inorder traversal of BST
#include <stdio.h>
#include <stdlib.h>

// Given Node node
struct node {
    int key;
    struct node *left, *right;
};

// Function to create a new BST node
struct node* newNode(int item)
{
    struct node* temp
        = (struct node*)malloc(
            sizeof(struct node));
    temp->key = item;
    temp->left = temp->right = NULL;
    return temp;
}

// Function to insert a new node with
// given key in BST
struct node* insert(struct node* node, int key)
{
    // If the tree is empty, return a new node
    if (node == NULL)
        return newNode(key);

    // Otherwise, recur down the tree
    if (key < node->key) {
        node->left = insert(node->left, key);
    }
    else if (key > node->key) {
        node->right = insert(node->right, key);
    }

    // Return the node pointer
    return node;
}

// Function to do inorder traversal of BST
void inorder(struct node* root)
{
    if (root != NULL) {
        inorder(root->left);
        printf("%d ", root->key);
        inorder(root->right);
    }
}

// Driver Code
int main()
{
    /* Let us create following BST 
              50 
           /     \ 
          30      70 
         /  \    /  \ 
       20   40  60   80 
   */
    struct node* root = NULL;

    // Creating the BST
    root = insert(root, 50);
    insert(root, 30);
    insert(root, 20);
    insert(root, 40);
    insert(root, 70);
    insert(root, 60);
    insert(root, 80);

    // Function Call
    inorder(root);

    return 0;
}

Java

import java.io.*;

// Java program for Inorder Traversal
class GFG {

    // Given Node node
    static class node {
        int key;
        node left, right;
    };

    // Function to create a new BST node
    static node newNode(int item)
    {
        node temp = new node();
        temp.key = item;
        temp.left = temp.right = null;
        return temp;
    }

    // Function to insert a new node with
    // given key in BST
    static node insert(node node, int key)
    {
        // If the tree is empty, return a new node
        if (node == null)
            return newNode(key);

        // Otherwise, recur down the tree
        if (key < node.key) {
            node.left = insert(node.left, key);
        }
        else if (key > node.key) {
            node.right = insert(node.right, key);
        }

        // Return the node
        return node;
    }

    // Function to do inorder traversal of BST
    static void inorder(node root)
    {
        if (root != null) {
            inorder(root.left);
            System.out.print(" " + root.key);
            inorder(root.right);
        }
    }

    // Driver Code
    public static void main(String[] args)
    {

        /* Let us create following BST
                50
             /     \
            30      70
           /  \    /  \
         20   40  60   80
     */
        node root = null;

        // inserting value 50
        root = insert(root, 50);

        // inserting value 30
        insert(root, 30);

        // inserting value 20
        insert(root, 20);

        // inserting value 40
        insert(root, 40);

        // inserting value 70
        insert(root, 70);

        // inserting value 60
        insert(root, 60);

        // inserting value 80
        insert(root, 80);

        // print the BST
        inorder(root);
    }
}
// This code is contributed by abhijitjadhav1998

Python3

# Python program to implement
# inorder traversal of BST

# Given Node node
class Node:
    def __init__(self, key):
        self.key = key
        self.left = None
        self.right = None

# Function to create a new BST node
def newNode(item):
    temp = Node(item)
    temp.key = item
    temp.left = temp.right = None
    return temp

# Function to insert a new node with
# given key in BST
def insert(node, key):
    # If the tree is empty, return a new node
    if node is None:
        return newNode(key)

    # Otherwise, recur down the tree
    if key < node.key:
        node.left = insert(node.left, key)
    elif key > node.key:
        node.right = insert(node.right, key)

    # Return the node pointer
    return node

# Function to do inorder traversal of BST
def inorder(root):
    if root:
        inorder(root.left)
        print(root.key, end=" ")
        inorder(root.right)

# Driver Code
if __name__ == '__main__':
    
    # Let us create following BST 
    #          50 
    #       /     \ 
    #     30      70 
    #    /  \    /  \ 
    #  20   40  60   80 
    root = None

    # Creating the BST
    root = insert(root, 50)
    insert(root, 30)
    insert(root, 20)
    insert(root, 40)
    insert(root, 70)
    insert(root, 60)
    insert(root, 80)

    # Function Call
    inorder(root)
#This code is contributed by japmeet01

Output

 20 30 40 50 60 70 80

Time Complexity: O(N), where N is the number of nodes of the BST
Auxiliary Space: O(1)

Introduction to Binary Search Tree – Data Structure and Algorithm Tutorials

Binary Search Tree is a data structure used in computer science for organizing and storing data in a sorted manner. Binary search tree follows all properties of binary tree and its left child contains values less than the parent node and the right child contains values greater than the parent node. This hierarchical structure allows for efficient Searching, Insertion, and Deletion operations on the data stored in the tree.

Binary Search Tree

Table of Content

What is Binary Search Tree?
Properties of Binary Search Tree
Handling duplicate values in the Binary Search Tree
Operations performed on a BST

1. Searching a node in BST
2. Insert a node into a BST
3. Delete a Node of BST
4. Traversal (Inorder traversal of BST)

Applications of BST
Advantages
Disadvantages
FAQ’s (Frequently asked questions) on Binary Search Tree:

Traversal (Inorder traversal of BST)

Introduction to Binary Search Tree – Data Structure and Algorithm Tutorials

Similar Reads