CODEWITHSUNDEEP
javarecursionbinary-tree
RShome
RShome

Reputation: 537

How to write a function that checks if a given binary search tree contains a given value?

For example, for the following tree:

n1 (Value: 1, Left: null, Right: null) n2 (Value: 2, Left: n1, Right: n3) n3 (Value: 3, Left: null, Right: null) Call to contains(n2, 3) should return true since a tree with root at n2 contains number 3.

I am new to programming and trying to solve the challenge to understand the concepts of programming. This is not a homework problem.

I have written the code below but it always returns false.

class Node {
   public int value;
   public Node left, right;

   public Node(int value, Node left, Node right) {
     this.value = value;
     this.left = left;
     this.right = right;
   }
  }

 public class BinaryTree {

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

  public static void main(String[] args) {

        Node n1 = new Node(1, null, null);
        Node n3 = new Node(3, null, null);
        Node n2 = new Node(2, n1, n3);

        System.out.println(contains(n2,3));
    }
 }

Upvotes: 0

Views: 1928

Answers (1)

Syrius
Syrius

Reputation: 941

You're missing the check if the value at a node corresponds to the value that you search. So you basically always return false because at one point root will be equal to null. To avoid this you need an else if clause where you check the value of the node and searched value and return true if this two are equal.

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

Upvotes: 2

Related Questions