Answer to Question #289363 in Java | JSP | JSF for Alma

Question

Implement BST using linked list.

Methods included:

1. insertNode,
2. traversal – Preorder, Postorder and Inorder Traversal
3. total number of nodes in BST 
4. total values of ALL NODES ( assuming all nodes contain integer values)
5. average
6. find min/max
7. find height of the tree

Answer 1

public class BST {
    private Node root;
    private int size;
    private double sum;

    public BST() {
        root = null;
        size = 0;
        sum = 0;
    }

    public void insert(int data) {
        if (root == null) {
            root = new Node(data);
        } else {
            Node cur = root;
            while (true) {
                if (cur.data >= data) {
                    if (cur.left == null) {
                        cur.left = new Node(data);
                        break;
                    } else {
                        cur = cur.left;
                    }
                } else {
                    if (cur.right == null) {
                        cur.right = new Node(data);
                        break;
                    } else {
                        cur = cur.right;
                    }
                }
            }
        }

        size++;
        sum += data;
    }

    public void preorder() {
        preorder(root);
    }

    private void preorder(Node node) {
        if (node == null) {
            return;
        }
        System.out.println(node.data);
        preorder(node.left);
        preorder(node.right);
    }

    public void postorder() {
        postorder(root);
    }

    private void postorder(Node node) {
        if (node == null) {
            return;
        }
        postorder(node.left);
        postorder(node.right);
        System.out.println(node.data);
    }

    public void inorder() {
        inorder(root);
    }

    private void inorder(Node node) {
        if (node == null) {
            return;
        }
        inorder(node.left);
        System.out.println(node.data);
        inorder(node.right);
    }

    public int size() {
        return size;
    }

    public int total() {
        return (int) sum;
    }

    public double average() {
        return sum / size;
    }

    public int min() {
        Node cur;
        for (cur = root; cur.left != null; cur = cur.left) {
        }
        return cur.data;
    }

    public int max() {
        Node cur;
        for (cur = root; cur.right != null; cur = cur.right) {
        }
        return cur.data;
    }

    public int height() {
        return findHeight(root);
    }

    private int findHeight(Node node) {
        if (node == null) {
            return -1;
        }

        int leftHeight = findHeight(node.left);
        int rightHeight = findHeight(node.right);

        if (leftHeight > rightHeight) {
            return leftHeight + 1;
        } else {
            return rightHeight + 1;
        }
    }

    static class Node {
        int data;
        Node left;
        Node right;

        Node(int data) {
            this.data = data;
            left = null;
            right = null;
        }
    }

}