How to find a Node of a Binary Search Tree without using a recursive method

Question

If I have a Method that only takes value as an argument (not Node) called public Node finder (E val) how can I find the respective Node regardless of the height and width of the tree. If the method took Node as an argument then it would be an easy solution to use recursion. But unfortunately I am not allowed to change the method signature. How can I do this the smart way rather than the dumb way I am trying below which would just end up with a ton of embedded if functions

public class BinarySearchTree<E extends Comparable<E>> {
    class Node {
        E value;
        Node leftChild = null;
        Node rightChild = null;
        Node(E value) {
            this.value = value;
        }
    }

    public Node finder(E val) {
        
        if (val == null) return null;
        if (root == null) return null;
        
        boolean flag = false;  
        Node temp = root;
        
        //find if Root Node matches value
        if(temp.value.compareTo(val) == 0) {
            flag = true;
            return temp;
        } 
        //if value is less than root check the left branch
        else if (temp.value.compareTo(val) > 0) {
            
            if(temp.leftChild.value.compareTo(val) == 0) {
                flag = true;
                return temp.leftChild;
            } 
            //more if statements here
        } 
        //if value is more than root check the right branch 
        else {
            if(temp.rightChild.value.compareTo(val) == 0) {
                flag = true;
                return temp.rightChild;
            }
            
            //more if statements here
        }
        
        return null;
    }
}

You can always turn a recursive function into an iterative one with an explicit Stack<Node> and pushing "to be visited nodes" in there — roookeee
– roookeee, Commented Jun 20, 2020 at 21:31
@roookeee thank you for the suggestion! Would you mind posting a brief sample of code as to how you would implement this solution? — FinDev
– FinDev, Commented Jun 20, 2020 at 21:33

recrsn · Accepted Answer · 2020-06-20 21:38:20Z

7

Binary search trees have this interesting property:

The left subtree of a node contains only nodes with values lesser than the node’s value.
The right subtree of a node contains only nodes with value greater than the node’s key.

Assuming your class BinarySearchTree holds a reference to the root, you can traverse the binary tree iteratively till you either reach the value or reach a leaf node which means your value does not exist in your binary search tree. The time complexity of this search operation is O(log(n)).

Here's some pseudocode

Find-Node(val):

    node = root
    while node != null:
      if val == node.val then return root
      if val < node.val then node = node.left
      if val > node.val then node = node.right

    return null

answered Jun 20, 2020 at 21:38

recrsn

4905 silver badges13 bronze badges

Sign up to request clarification or add additional context in comments.

Collectives™ on Stack Overflow

How to find a Node of a Binary Search Tree without using a recursive method

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related