package main

import "fmt"

// Node structure
type Node struct {
    data  int
    left  *Node
    right *Node
}

// BST structure
type BST struct {
    root *Node
}

// Insert operation
func (bst *BST) Insert(data int) {
    bst.root = insert(bst.root, data)
}

func insert(node *Node, data int) *Node {
    if node == nil {
        return &Node{data: data}
    }
    
    if data < node.data {
        node.left = insert(node.left, data)
    } else if data > node.data {
        node.right = insert(node.right, data)
    }
    
    return node
}

// Inorder traversal
func (bst *BST) InorderTraversal() {
    inorder(bst.root)
}

func inorder(node *Node) {
    if node != nil {
        inorder(node.left)
        fmt.Printf("%d ", node.data)
        inorder(node.right)
    }
}

func main() {
    bst := &BST{}
    
    // Insert elements
    bst.Insert(5)
    bst.Insert(3)
    bst.Insert(7)
    bst.Insert(1)
    bst.Insert(9)
    
    // Print inorder traversal
    fmt.Println("Inorder Traversal:")
    bst.InorderTraversal()
}

public class BinarySearchTree {
    class Node {
        int data;
        Node left, right;
        
        public Node(int data) {
            this.data = data;
            left = right = null;
        }
    }
    
    Node root;
    
    BinarySearchTree() {
        root = null;
    }
    
    // Insert operation
    void insert(int data) {
        root = insertRec(root, data);
    }
    
    Node insertRec(Node root, int data) {
        if (root == null) {
            root = new Node(data);
            return root;
        }
        
        if (data < root.data)
            root.left = insertRec(root.left, data);
        else if (data > root.data)
            root.right = insertRec(root.right, data);
        
        return root;
    }
    
    // Inorder traversal
    void inorder() {
        inorderRec(root);
    }
    
    void inorderRec(Node root) {
        if (root != null) {
            inorderRec(root.left);
            System.out.print(root.data + " ");
            inorderRec(root.right);
        }
    }
    
    public static void main(String[] args) {
        BinarySearchTree bst = new BinarySearchTree();
        
        // Insert elements
        bst.insert(5);
        bst.insert(3);
        bst.insert(7);
        bst.insert(1);
        bst.insert(9);
        
        // Print inorder traversal
        System.out.println("Inorder Traversal:");
        bst.inorder();
    }
}

class Node:
    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None

class BinarySearchTree:
    def __init__(self):
        self.root = None
    
    def insert(self, data):
        self.root = self._insert_recursive(self.root, data)
    
    def _insert_recursive(self, root, data):
        if root is None:
            return Node(data)
        
        if data < root.data:
            root.left = self._insert_recursive(root.left, data)
        elif data > root.data:
            root.right = self._insert_recursive(root.right, data)
        
        return root
    
    def inorder_traversal(self):
        self._inorder_recursive(self.root)
    
    def _inorder_recursive(self, root):
        if root:
            self._inorder_recursive(root.left)
            print(root.data, end=" ")
            self._inorder_recursive(root.right)

# Example usage
if __name__ == "__main__":
    bst = BinarySearchTree()
    
    # Insert elements
    bst.insert(5)
    bst.insert(3)
    bst.insert(7)
    bst.insert(1)
    bst.insert(9)
    
    # Print inorder traversal
    print("Inorder Traversal:")
    bst.inorder_traversal()