Using an object-oriented language of your choice, build a class called BST with

Question

Using an object-oriented language of your choice, build a class called BST with the following methods:

1. void add(int i)

2. bool contains(int i)

3. void inOrderTraversal() /* writes the values of the tree to standard output using an in-order traversal */

4. void preOrderTraversal() /* writes the values of the tree to standard output using a pre-order traversal */

5. void postOrderTraversal() /* writes the values of the tree to standard output using a post-order traversal */

Include a separate class with a main method that demonstrates all of the class’ functionality. You may implement the BST with either an array or a linked structure.

Explanation / Answer

I have used JAVA for implementing this BST

since you have specified single or double linked list

I have used double linked list(which is nothing but a node in BST using class)

class BST {
    class Node {
        int key;
        Node left, right;

        public Node(int item) {
            key = item;
            left = right = null;
        }
    }
    Node root;

    BST() {
        root = null;
    }
    boolean contains(int value){
        return iscontain(root,value);
    }
  
    boolean iscontain(Node root,int value){
        if (root == null) {
            return false;
        }
        if(value == root.key)
            return true;
        if (value < root.key)
            return iscontain(root.left, value);
        else
            return iscontain(root.right, value);
    }
    void add(int key) {
       root = addNode(root, key);
    }
    Node addNode(Node root, int key) {

        if (root == null) {
            root = new Node(key);
            return root;
        }

        if (key < root.key)
            root.left = addNode(root.left, key);
        else if (key > root.key)
            root.right = addNode(root.right, key);
        return root;
    }
    void inorderTraversal() {
        System.out.print(" In-order Traversal is: ");
       inorderRecursion(root);
    }
    void inorderRecursion(Node root) {
        if (root != null) {
            inorderRecursion(root.left);
            System.out.print(root.key +" ");
            inorderRecursion(root.right);
        }
    }

void preorderTraversal() {
       System.out.print(" Pre-order Traversal is: ");
       preorderRecursion(root);
    }
    void preorderRecursion(Node root) {
        if (root != null) {
           System.out.print(root.key +" ");
            preorderRecursion(root.left);
            preorderRecursion(root.right);
        }
    }
   void postorderTraversal() {
       System.out.print(" Post-order Traversal is: ");
        postorderRecursion(root);
    }
    void postorderRecursion(Node root) {
        if (root != null) {
            postorderRecursion(root.left);
            postorderRecursion(root.right);
           System.out.print(root.key + " ");
        }
    }

    public static void main(String[] args) {
        BST tree = new BST();
       tree.add(50);
        tree.add(30);
        tree.add(20);
        tree.add(40);
        tree.add(70);
        tree.add(60);
        tree.add(80);
        System.out.print(tree.contains(75));
        tree.inorderTraversal();
        tree.preorderTraversal();
        tree.postorderTraversal();
    }
}

the above program meets your criteria given in description

Output of the program will be :

false
In-order Traversal is: 20 30 40 50 60 70 80
Pre-order Traversal is: 50 30 20 40 70 60 80
Post-order Traversal is: 20 40 30 60 80 70 50

Related Questions

Navigate

• Browse (All)
• Browse U
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.