Question

In java, create a binary search tree (without using additional libraries) of stacks where each node contains a key and a stack. In this binary search tree, when adding a new element to the tree it is inserted based off of its key value; if that key value already exist then the element is pushed into the stack at that location, if the key value does not exist a node element is added to the tree to reflect that key, and a empty stack is created where you will push the element to be inserted. When removing elements from the tree, you will pop elements at that specific key until the stack is empty; when the stack becomes empty that node will be removed from the tree and one of its decedents need to take its place in the tree.

Answer 1

import java.util.Stack;

// class Node.

class Node {

    int key;

    Stack<Integer> stack;

    Node left, right;

    // constructor

    Node(int value) {

        key = value;

        stack = new Stack<Integer>();

        left = right = null;

    }

}

public class BinaryTree {

    Node root;

    BinaryTree() {

        root = null;

    }

    void insert(int key) {

        root = recInsert(root, key);

    }

    public Node recInsert(Node root, int key) {

        if (root == null) {

            root = new Node(key);

            return root;

        }

        if (root.key == key) {

            root.stack.add(key);

            return root;

        }

        if (key < root.key) {

            root.left = recInsert(root.left, key);

        }

        else if (key > root.key) {

            root.right = recInsert(root.right, key);

        }

        return root;

    }

    void deleteKey(int key) {

        root = checkDelete(root, key);

    }

    Node checkDelete(Node root, int key) {

        if (root == null) {

            return root;

        }

        if (key < root.key)

            root.left = recDelete(root.left, key);

        else if (key > root.key)

            root.right = recDelete(root.right, key);

        else {

            if (!root.stack.isEmpty()) {

                root.stack.pop();

                return root;

            }

            else {

                root = recDelete(this.root, key);

            }

        }

        return root;

    }

    Node recDelete(Node root, int key) {

        if (root == null) {

            return root;

        }

        if (key < root.key)

            root.left = recDelete(root.left, key);

        else if (key > root.key)

            root.right = recDelete(root.right, key);

        else {

            if (root.left == null)

                return root.right;

            else if (root.right == null)

                return root.left;

            root.key = findMin(root.right);

            root.right = recDelete(root.right, root.key);

        }

        return root;

    }

    int findMin(Node root) {

        int min = root.key;

        while (root.left != null) {

            min = root.left.key;

            root = root.left;

        }

        return min;

    }

    void inorder() {

        recInorder(root);

        System.out.println();

    }

    void recInorder(Node root) {

        if (root != null) {

            recInorder(root.left);

            System.out.print(root.key + " ");

            recInorder(root.right);

        }

    }

    public static void main(String[] args) {

        BinaryTree bt = new BinaryTree();

        bt.insert(4);

        bt.insert(8);

        bt.insert(4);

        bt.insert(4);

        bt.insert(2);

        bt.insert(10);

        bt.insert(6);

        bt.insert(12);

        bt.inorder();

        bt.deleteKey(4);

        bt.inorder();

        bt.deleteKey(4);

        bt.inorder();

        bt.deleteKey(4);

        bt.inorder();

    }

}

PLEASE LIKE IT RAISE YOUR THUMBS UP
IF YOU ARE HAVING ANY DOUBT FEEL FREE TO ASK IN COMMENT SECTION