[Testdome] binary search tree

While my overall logic is correct, it isnt time eff. I checked the recursion to go on as long as root.left!=null as I have seen in the 3 traversal solution in baekjoon. However, i would be recurring even when root.left’s value is less than the value we are looking for. This leads to unnecessary deep traversals.

my runtime code but correct:

    public static boolean contains(Node root, int value) {
        if (root == null) {
            return false;
        }

        if (root.value == value) {
            return true;
        }

        if (root.left != null && contains(root.left, value)) {
            return true;
        }

        if (root.right != null && contains(root.right, value)) {
            return true;
        }

        return false;
    }

What we want in the recursive condition is to recur only if root.value > value, then we recur for root.left since root isnt the answer. But else, we recur for root.right since the value we are looking for is bigger than root’s value.

better solution

    public static boolean contains(Node root, int value) {
        if(root == null) return false;
        if(root.value == value) return true;
        if(root.value > value) return contains(root.left, value);
        return contains(root.right, value);
    }