Best algorithm to search Binary Search Tree (BST)

0
votes

I have a Binary Search Tree and each of its node has two values.

int value;
String name;

So its node is like this.

class Node {
        int value;
        String name;
        Node left, right;
}

I have inserted values in BST according to the ascending order of "name" variable of node. So inorder traversal of tree will return the nodes in ascending order of "name".

Now I want to display the tree nodes according to ascending order of "value" variable. Without changing the original tree. What algorithm/approach will be most efficient for this?

2
javaalgorithmsortingdata-structuresbinary-search-tree
What you are looking for is a regular sorting algorithm. The tree offers no help here. – Captain Giraffe
So I should make an array instead of tree? – Haseeb Ahmad
Actually it is part of my assignment to use BST. That's why I can't use any other data structure. – Haseeb Ahmad
Then you need to recreate the tree with a new comparator for value. Your current tree with comparator for name is of no value to you. – Captain Giraffe
It seems a good approach. Thanks bro. Lets see if somebody else can guide me with a better solution. Otherwise I will use your solution. – Haseeb Ahmad

2 Answers

0
votes

Use TreeSet with a comparator that sort ascending based on the name and traverse the nodes from left to right, like this:

You can use recursion version

    public static Iterable<Node> order(Node root) {
        Comparator<Node> cmp = (node1, node2) -> node1.name.compareTo(node2.name);
        TreeSet<Node> set = new TreeSet<>(cmp);
        visit(set, root);
        return set;
    }

    public static void visit(TreeSet<Node> set, Node node) {
        if (node == null)
            return;
        set.add(node);
        visit(set, node.left);
        visit(set, node.right);
    }

, or Queue version

    public static Iterable<Node> order(Node root) {
        Comparator<Node> cmp = (node1, node2) -> node1.name.compareTo(node2.name);
        Queue<Node> queue = new ArrayDeque<>();
        TreeSet<Node> set = new TreeSet<>(cmp);
        queue.add(root);
        set.add(root);
        while (!queue.isEmpty()) {
            Node node = queue.poll();
            if (node.left != null) {
                queue.add(node.left);
                set.add(node.left);
            }

            if (node.right != null) {
                queue.add(node.right);
                set.add(root);
            }
        }
        return set;
    }
0
votes

This should work:

void addToTree(Node Tree, Node x){
    if (Tree.value < x.value){
        if (Tree.right == null){
            Tree.right = x
        } else {
            addToTree(Tree.right, x)
        }
    } else if (Tree.value > x.value) {
        if (Tree.left == null){
            Tree.left = x
        } else {
            addToTree(Tree.left, x)
        }
    } else {
        throw new Exception("Value already exists.")
    }
}

Node getFromTree(Node Tree, int x){
    if (Tree.value < x.value){
        if (Tree.right == null){
            throw new Exception("Value doesn't exist.")
        } else {
            return getFromTree(Tree.right, x)
        }
    } else if (Tree.value > x.value){
        if (Tree.left == null){
            throw new Exception("Value doesn't exist.")
        } else {
            return getFromTree(Tree.left, x)
        }
    } else {
        return Tree
    }
}

It sorts and finds Nodes, by their value (Node.value).