Demo entry 6350148

lalala

   

Submitted by anonymous on Mar 06, 2017 at 18:15
Language: Java. Code size: 3.4 kB.

public class BinarySearchTree{
    TreeNode root = null;

    class TreeNode {
        public int myValue;
        public TreeNode myLeft;
        public TreeNode myRight;

        public TreeNode(int val) {
            myValue = val;
        }
    }
    // adds inputted value as new node to BST
    public void add(int newValue) {
        if (root == null) {
            root = new TreeNode(newValue);
        }
        else {
            add(newValue, root);
        }
    }
    public void add(int newValue, TreeNode current) {
        if (newValue > current.myValue) {
            if (current.myRight != null) {
                add(newValue, current.myRight);
            }
            else {
                current.myRight = new TreeNode(newValue);
            }
        }
        if (newValue < current.myValue) {
            if (current.myLeft != null) {
                add(newValue, current.myLeft);
            }
            else {
                current.myLeft = new TreeNode(newValue);
            }
        }
    }
    // prints a String showing structure of this tree 
    public String toString() {
        return toString(root, "");
    }
    public String toString(TreeNode current, String level) {
        String leftString = "null";
        String rightString = "null";

        if (current.myLeft != null) {
            leftString = toString(current.myLeft, level+"   ");
        }
        if (current.myRight != null) {
            rightString = toString(current.myRight, level+"   ");
        }
        return current.myValue + "\n" + level + "L: " + leftString + "\n" + level + "R: " + rightString;
    }
    // counts total number of nodes in this tree
    public int countNodes() {
        return countNodes(root);
    }
    public int countNodes(TreeNode current) {
        if (current == null) {
            return 0;
        }
        int L = countNodes(current.myLeft);
        int R = countNodes(current.myRight);

        return 1+L+R;
    }
    // returns the height of a tree
    public int computeHeight() {
        return computeHeight(root);
    }
    private int computeHeight(TreeNode current) {
        if (current == null) {
            return 0;
        }
        int L = computeHeight(current.myLeft);
        int R = computeHeight(current.myRight);
        if (L>R) {
            return 1+L;
        }
        else {
            return 1+R;
        }
    }
    // returns true if input value can be found in tree 
    public boolean containsNode(int value) {
        return containsNode(root, value);
    }
    private boolean containsNode(TreeNode current, int value) {
        if (current == null) {
            return false;
        }
        if (current.myValue==value) {
            return true;
        }
        boolean L = containsNode(current.myLeft, value);
        boolean R = containsNode(current.myRight, value);
        if (L || R) {
            return true;
        }
        return false;
    }
    // returns the largest value in the tree 
    public int findMax() {
        return findMax(root);
    }
    private int findMax(TreeNode current) {
        if (current.myRight==null) {
            return current.myValue;
        }
        return findMax(current.myRight);
    }
}

This snippet took 0.01 seconds to highlight.

Back to the Entry List or Home.

Delete this entry (admin only).