Question

I require some assistance with the following problem:

Create a binary search tree for 6 randomly chosen vegetables.

- Carrots

- Green beans

- Cucumber

- Corn

- Peas

- Spinach

Thank you.

Answer 1

In a Binary Search Tree, every node has at most a left child and a right child. Every node on the left of a given node is smaller than it, and every node on the right of a given node is greater than it.

Since you have to create a BST of Strings, if the String that needs to be inserted comes before (alphabetically) the String in the current node then it will be considered smaller than the current node and will be placed on its left. Similarly, if it comes after the current node String alphabetically it will be placed on its right,

For example, After inserting "Carrots", since "Green Beans" comes after "Carrots" alphabetically it will be considered larger than Carrots and will be placed on its right.

This is how your BST will look like after inserting the elements.

The following is the code for the same in JAVA for your reference:

class BST {

    Node root;

    static class Node {
        String key;
        Node left, right;

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

    BST() {
        root = null;
    }

    void insert(String key) {
        root = insertRec(root, key);
    }

    Node insertRec(Node root, String key) {

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

        if (key.compareTo(root.key) < 0)
            root.left = insertRec(root.left, key);
        else if (key.compareTo(root.key) > 0)
            root.right = insertRec(root.right, key);

        return root;
    }

    void printPreorder() {
        printPreorder(root);
    }

    void printPreorder(Node node) {
        if (node == null)
            return;
        System.out.print(node.key + " ");
        printPreorder(node.left);
        printPreorder(node.right);
    }

    public static void main(String[] args) {
        BST tree = new BST();
        tree.insert("Carrots");
        tree.insert("Green Beans");
        tree.insert("Cucumber");
        tree.insert("Corn");
        tree.insert("Peas");
        tree.insert("Spinach");

        tree.printPreorder();

    }
}