CODEWITHSUNDEEP
javatreebinary-treenodes
FinDev
FinDev

Reputation: 439

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

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;
    }
}

Upvotes: 0

Views: 1616

Answers (1)

recrsn
recrsn

Reputation: 480

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

Upvotes: 7

Related Questions