DEV Community

Matt Ryan
Matt Ryan

Posted on

2 2

Day 47: Binary Search Tree

Constructor:

    public BinarySearchTree() {
        root = null;
    }
Enter fullscreen mode Exit fullscreen mode

Check to see if tree is empty:

    public boolean isEmpty() {
        return root == null;
    }
Enter fullscreen mode Exit fullscreen mode

Insert data:

    public void insert(int data) {
        root = insert(root, data);
    }
Enter fullscreen mode Exit fullscreen mode

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;
    }
Enter fullscreen mode Exit fullscreen mode

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;
    }
Enter fullscreen mode Exit fullscreen mode

Count the nodes:

    public int countNodes() {
        return countNodes(root);
    }
Enter fullscreen mode Exit fullscreen mode

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;
        }
    }
Enter fullscreen mode Exit fullscreen mode

Search the tree:

    public boolean search(int val) {
        return search(root, val);
    }
Enter fullscreen mode Exit fullscreen mode

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;
    }
Enter fullscreen mode Exit fullscreen mode

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);
        }
    }
Enter fullscreen mode Exit fullscreen mode

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);
        }
    }
Enter fullscreen mode Exit fullscreen mode

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);
        }
    }
}
Enter fullscreen mode Exit fullscreen mode

Top comments (0)

Great read:

Is it Time to go Back to the Monolith?

History repeats itself. Everything old is new again and I’ve been around long enough to see ideas discarded, rediscovered and return triumphantly to overtake the fad. In recent years SQL has made a tremendous comeback from the dead. We love relational databases all over again. I think the Monolith will have its space odyssey moment again. Microservices and serverless are trends pushed by the cloud vendors, designed to sell us more cloud computing resources.

Microservices make very little sense financially for most use cases. Yes, they can ramp down. But when they scale up, they pay the costs in dividends. The increased observability costs alone line the pockets of the “big cloud” vendors.