CODEWITHSUNDEEP
algorithmtree
anondumpster
anondumpster

Reputation: 13

Finding if a value is contained in a binary tree

I have a class TreeNode as shown below: 

class TreeNode {
    int value;
    TreeNode left;
    TreeNode right;

public TreeNode(int x) {
    value = x;
}

I want to write a recursive method contains(int i) that will return true if i is the value of a node in the tree, and false otherwise.

From my understanding, a binary tree does not have to be ordered, so I shouldn't be comparing the value of the current node to the value we are searching for. Therefore I wrote the following method:

public boolean contains(int i) {
    if (value == x) {
        return true;
    } else {
        if (left != null) {
            return left.find(i);
        }
        if (right != null) {
            return right.find(i);
        }
    }
    return false;
}

My thoughts behind this were that it would check if the value of the current node is equal to the value we are searching for, and if not then it should recursively call the method with the left and right nodes if they are not null, otherwise the method will return false.

This method ultimately returns true if we are searching for a value that corresponds to a node on the left of the tree, however once we search for a value beyond this (towards the right), it will return false. I've been picking my brain for hours on this and I'm sure there's a relatively trivial solution but I can't seem to get to it.

Upvotes: 1

Views: 1671

Answers (7)

Radoslav Mitev
Radoslav Mitev

Reputation: 62

Although, I would rather make a second static method which has as parameters TreeNode and int, the right fix for your method is something like this:

public boolean contains(int i) {
    if (value == x) {
        return true;
    }

    if (left != null && left.find(i)) {
        return true;
    }
    if (right != null && right.find(i)) {
        return true;
    }

    return false;
}

The error in your code is that you don't give a chance to the right sub-tree, if left sub-tree does not contain the value. Don't return a value, if you are NOT SURE that there aren't any other results.

Upvotes: 0

Konstantin Yovkov
Konstantin Yovkov

Reputation: 62864

Your code doesn't seem to complile, because the TreeNode class doesn't have a find(int i) method.

I think the contains() method should rather look like:

public boolean contains(TreeNode node, int i) {
  boolean result = node.value == i;
  if (left != null) result |= contains(node.left, i);
  if (right != null) result |= contains(node.right, i);
  return result;
}

Of course, you can terminate once the value is found and skip the two != null checks, by adding an additional recursion bottom in the beggining of the method:

public boolean contains(TreeNode node, int i) {
  if (node == null) return false;
  if (node.value == i) return true;
  return contains(node.left, i) || contains(node.right, i);
}

which can be further simplified to a one-liner:

public boolean contains(TreeNode node, int i) {
  return node != null && 
        (node.value == i || contains(node.left, i) || contains(node.right, i));
}

Upvotes: 0

Henry
Henry

Reputation: 43738

Something like this:

public boolean contains(int i) {
    return value == i ||
       left != null && left.contains(i) ||
       right != null && right.contains(i);
}

Upvotes: 1

Codor
Codor

Reputation: 17605

Your implementation prefers the left subtree; it does not properly search in both subtrees. This can be fixed as follows.

public boolean contains(int i) {
    boolean Result = value == x;
    if (left != null) {
        Result |= left.find(i);
    }
    if (right != null) {
        Result |= right.find(i);
    }
    return Result;
}

This implementation can be optimized further as follows to return early.

public boolean contains(int i) {
    boolean Result = value == x;
    if (!Result && left != null) {
        Result |= left.find(i);
    }
    if (!Result && right != null) {
        Result |= right.find(i);
    }
    return Result;
}

Upvotes: 0

Ben R.
Ben R.

Reputation: 2155

    if (left != null) {
        return left.find(i);
    }

This is the issue. If there's both a left AND a right node, the code will only return whether anything was found on the left side.

Instead, you want something like:

    boolean found = false;
    if (left != null) {
        found = left.find(i);
    }
    if (!found && right != null) {
        found = right.find(i);
    }
    return found;

Upvotes: 0

Maurice Perry
Maurice Perry

Reputation: 9650

This seems more correct:

public boolean contains(int i) {
    if (value == x) {
        return true;
    } else {
        if (left != null && left.find(i)) {
            return true;
        }
        if (right != null && right.find(i)) {
            return true;
        }
    }
    return false;
}

Upvotes: 0

Eran
Eran

Reputation: 393841

It is incorrect to return the result of the recursive call without checking first if it's true or false.

You should still search the right sub-tree if the left sub-tree search returns false. 

public boolean contains(int i) {
    if (value == x) {
        return true;
    } else {
        boolean found = false;
        if (left != null) {
            found = left.find(i);
        }
        if (!found && right != null) {
            found right.find(i);
        }
        return found;
    }
}

Upvotes: 0

Related Questions