Day 47: Binary Search Tree

Constructor:

    public BinarySearchTree() {
        root = null;
    }

Check to see if tree is empty:

    public boolean isEmpty() {
        return root == null;
    }

Insert data:

    public void insert(int data) {
        root = insert(root, data);
    }

Insert data recursively:

    private BSTNode insert(BSTNode node, int data) {
        if (node == null) {
            node = new BSTNode(data);
        } else if (data <= node.getData()) {
            node.left = insert(node.left, data);
        } else {
            node.right = insert(node.right, data);
        }
        return node;
    }

Delete data:

    public void delete(int k) {
        if (isEmpty()) {
            System.out.println("Tree Empty");
        } else if (search(k) == false) {
            System.out.println("Sorry " + k + " is not present");
        } else {
            root = delete(root, k);
            System.out.println(k + " deleted from the tree");
        }
    }

    private BSTNode delete(BSTNode root, int k) {
        BSTNode p, p2, n;
        if (root.getData() == k) {
            BSTNode lt, rt;
            lt = root.getLeft();
            rt = root.getRight();
            if (lt == null && rt == null) {
                return null;
            } else if (lt == null) {
                p = rt;
                return p;
            } else if (rt == null) {
                p = lt;
                return p;
            } else {
                p2 = rt;
                p = rt;
                while (p.getLeft() != null) {
                    p = p.getLeft();
                }
                p.setLeft(lt);
                return p2;
            }
        }
        if (k < root.getData()) {
            n = delete(root.getLeft(), k);
            root.setLeft(n);
        } else {
            n = delete(root.getRight(), k);
            root.setRight(n);
        }
        return root;
    }

Count the nodes:

    public int countNodes() {
        return countNodes(root);
    }

Count the nodes recursively:

    private int countNodes(BSTNode r) {
        if (r == null) {
            return 0;
        } else {
            int l = 1;
            l += countNodes(r.getLeft());
            l += countNodes(r.getRight());
            return l;
        }
    }

Search the tree:

    public boolean search(int val) {
        return search(root, val);
    }

Search the tree recursively:

    private boolean search(BSTNode r, int val) {
        boolean found = false;
        while ((r != null) && !found) {
            int rval = r.getData();
            if (val < rval) {
                r = r.getLeft();
            } else if (val > rval) {
                r = r.getRight();
            } else {
                found = true;
                break;
            }
            found = search(r, val);
        }
        return found;
    }

Tree Traversals:

Inorder traversal

    public List<BSTNode> inorder() {
        List<BSTNode> walk = new ArrayList<>();
        inorder(root, walk);
        return walk;
    }

    private void inorder(BSTNode r, List<BSTNode> walk) {
        if (r != null) {
            inorder(r.getLeft(), walk);
            System.out.print(r.getData() + " ");
            walk.add(r);
            inorder(r.getRight(), walk);
        }
    }

Preorder

    public List preorder() {
        List<BSTNode> walk = new ArrayList<>();
        preorder(root, walk);
        return walk;
    }

    private void preorder(BSTNode r, List<BSTNode> walk) {
        if (r != null) {
            System.out.print(r.getData() + " ");
            walk.add(r);
            preorder(r.getLeft(), walk);
            preorder(r.getRight(), walk);
        }
    }

Postorder

    public List<BSTNode> postorder() {
        List<BSTNode> walk = new ArrayList<>();

        postorder(root, walk);
        return walk;
    }

    private void postorder(BSTNode r, List<BSTNode> walk) {
        if (r != null) {
            postorder(r.getLeft(), walk);
            postorder(r.getRight(), walk);
            System.out.print(r.getData() + " ");
            walk.add(r);
        }
    }
}