CODEWITHSUNDEEP
javabinary-search-tree
F.G
F.G

Reputation: 41

How to get the left and right child of a node in an unordered binary search tree?

I'm stuck with this problem: The method below must return the value in the left child node, or -1 if it not exist.

public int getLeftChild(int el) {...}
/* Same for the right child */

Now, the argument is an int value, that indicates the value of the parent node. Another issue is that... the tree is not ordered, and there are only positive integer values. So, I can have a value of 0 in the root, 3 in the left child and 1 in the right child, and so on... I can't figure out how to resolve this. I can't use ADTs like LinkedList or Stack for any purpose. The binary tree class has a field root, of type Node:

public class Node {
    private int value;
    private Node leftChild;
    private Node rightChild;
    /*Getters and Setters...*/
}

Upvotes: 0

Views: 1267

Answers (1)

dreamcrash
dreamcrash

Reputation: 51513

Something like this would work:

public int getLeftChild(int el) {
    int not_found = -1;
    Stack<Node> nodes_to_search = new Stack<>();
    nodes_to_search.add(this);

    while(!stack.isEmpty()){
        Node root = nodes_to_search.pop();
        if(root.value == el){
            return (root.leftChild != null) ? root.leftChild.value  : not_found;
        }
        if(root.leftChild != null)   nodes_to_search.push(root.leftChild);
        if(root.rightChild != null)  nodes_to_search.push(root.rightChild);
    }
    return not_found;
}

You have to search in both the left and right subtrees since the tree is not sorted. Every time you find a valid subtree (i.e., not null) you added to the stack of elements to search. You stop the search when your searching criteria is meet.

Upvotes: 0

Related Questions