CODEWITHSUNDEEP
javaalgorithmdata-structuresbinary-tree
мајдејсаремех
мајдејсаремех

Reputation: 536

How to find a value in binary expression tree?

Given a tree for example like:

enter image description here

How can I let's say find the value 3 (it doesn't matter which value of 3, but after one is found the search should conclude) in that tree and maybe change it to 7 or some other number, but after that stop traversing the tree? All of the algorithms I found online will always traverse the whole tree or when they search for a specific value then it's for a BST, which doesn't apply here. I cannot provide a code sample as I don't know where to start with this problem.

class Node {

    String value;
    Node left, right;

    Node(String item) {
        value = item;
        left = right = null;
    }

    boolean isLeaf() {
        return (left == null) && (right == null);
    }
}

Upvotes: 1

Views: 525

Answers (2)

isnot2bad
isnot2bad

Reputation: 24444

First, you need an algorithm to find a specific node based on its value. This can easily be done by traversing the tree in pre-order, in-order or post-order (see Tree Traversal on Wikipedia, especially Implementation of Depth-first search). This algorithm returns from recursion if the item has been found:

Node findNode(Node root, String value) {
    if (root == null) return null; // no such node
    if (value.equals(root.getValue())) return root; // the node itself contains the value

    Node n = findNode(root.getLeft(), value); // search left sub-tree
    if (n != null) return n; // we've found it in the left sub-tree

    return findNode(root.getRight(), value); // search right sub-tree
}

After that, it is easy to exchange a value in the tree:

void exchange(Node root, String value, String newValue) {
    Node n = findNode(root, value);
    n.setValue(newValue);
}

Of course you can also traverse the tree iteratively, but if you don't have very huge trees, there is no reason to not use the simpler recursive approach.

Upvotes: 3

mettleap
mettleap

Reputation: 1410

According to what you want, you will always have to start traversing your tree from the root element (I am assuming you have access to the root initially) in a sequential manner (like in BFS or DFS). Since your tree isn't a BST (or a tree having some special relations between the nodes), there's no way we can search for a particular node any faster than a normal sequential search over all the nodes.

Sample BFS pseudo-code;

Initialize Queue q;
q.add(root);

while(q is not empty){
    Node node = q.pop();

    if(Node equal to 3){ // or any value you want
        node.val = 7;
        return;
    }

    if(node.left!=null){q.add(node.left);}
    if(node.right!=null){q.add(node.right);}
}

Upvotes: 1

Related Questions