Searching in Pre Order Traversal way

Question

I have a binary search tree. I know how to search using the search property. But my task is to search the tree without using search property.(Say, search in binary tree) This is how I have to search.

1. If you find the value in the current node return it.

2. else search in right. If not found in right, then search in left

3. If not found in the whole tree return null.

This is what i tried.

public Node search(int val)
{
    Node target = this;
    if(target.getVal() == val)
        return this;
    else if(target.getRight() == null && target.getLeft() == null)
        return null;
    if(target.getRight() != null)
    {
        return target.getRight().search(id);
    }
    if(target.getLeft() != null)
    {
        return target.getLeft().search(id);
    }
    return null;
}

Problem with my code is, if right child exists and val is not found in right I'm getting null value. (Not searching in left). How to resolve this?

Answer 1

public Node search(int val)
{
    Node target = this;
    if(target.getVal() == val)
        return this;
    else if(target.getRight() == null && target.getLeft() == null)
        return null;
    if(target.getRight() != null)
    {
        return target.getRight().search(id); //here lies the problem
    }
    if(target.getLeft() != null)
    {
        return target.getLeft().search(id);
   }
return null;

}

The problem in your code is that you are returning the result of search in right subtree of the node being searched.

Here's the updated code

public Node search(int val)
{
    Node target = null;
    if(this.getVal() == val)
    {
        return this;
    }
    else if(this.getRight() == null && this.getLeft() == null)
        return target;
    if(this.getRight() != null)
    {
        target = this.getRight().search(id);
    }
    if(target==null && this.getLeft() != null)
    {
        target = this.getLeft().search(id);
   }
   return target;

}

Answer 2

This is untested code, but I'd change your logic a bit:

public Node search(int val)
{
    if(this.getVal() == val)
        return this;

    if (this.getRight() != null) {
        Node right = this.getRight().search(id);
        if (right != null)
            return right;
    }

    if (this.getLeft() != null) {
        Node left = this.getLeft().search(id);
        if (left != null)
            return left;
    }

    return null;
}

In your version you are returning a solution with the sole requirement that the node on the right or left is not null. You have to return a solution only if a solution is found.