java recursive parent search in a bintree

Question

I’m trying to search the parent node of a node with a certain value within my bintree in a recursive way.

I call my search method with the value of the child node and the root node as start.

I’m wondering if there is a more elegant way to prevent getting null as soon as the first node without any child is reached.

public Node getParent(int search, Node position) 
{

    if (search==root.getContent())
    {
        return null;
    }
    if (position.getRight()!=null)
    {
        if (position.getRight().getContent()==search)
        {
            return position;
        }
        if (!(position.getRight().getRight()==null&&position.getRight().getLeft()==null))
        {
            return getParent(search, position.getRight());
        }

    }

    if (position.getLeft()!=null)
    {
        if (position.getLeft().getContent()==search)
        {
            return position;
        }
        if (!(position.getLeft().getRight()==null&&position.getLeft().getLeft()==null))
        {
            return getParent(search, position.getLeft());
        }

    }

    return null;
}

Thanks for suggestions and explanation

Answer 1

I'm not fully understanding your example because it is a bit weird to have a position parameter instead of using this. Your question has two parts; let me start with

How can I avoid all these null pointers?

The object oriented way to avoid this is having a structure like this:

The Tree has a root which is just an Element. Element is an abstract class which is inherited by Node and Empty. Instead of null you can now use Empty and define the behavior there.

---

How can I search for the parent node of a node with value v?

I'd just implement a method getParentOf:

class Tree

/**
 * @return the parent of a given `value`.
 *         or -1 if there is no such parent
*/
public int getParentOf(int value) {
    return root.getParentOf();
}

class Element

/**
 * Returns the value or `-1` if this is an `Empty`.
*/
public abstract int getValue();
public abstract int getParentOf(int value);

class Node

private Element left;
private Element right;
private int content;

@Override
public int getParentOf(int value) {
    if (value > content) {
        if (right.getValue() == value) {
            return this.content;
        } else {
            return right.getParentOf(value);
        }
    } else if (value < content) {
        if (left.getValue() == value) {
            return this.content;
        } else {
            return left.getParentOf(value);
        }
    } else {
        // this is the node with `value`, however
        // it is the root so there is no parent of
        // this node
        throw new NoSuchElementException();
    }
}

public int getValue() {
    return content;
}

class Empty

@Override
public int getParentOf(int value) {
    // There is not even a node with `value`
    throw new NoSuchElementException();
}

@Override
public int getValue() {
    return -1;
}

You could of course use generics and so on here but I think it is easier to understand with just int.

Answer 2

At each node, you have three ways to obtain a non-null result:

1. If either of this node's children match the search target, you should return this node.

2. If a recursive search of this node's left child returns a non-null value, you should return that.

3. If a recursive search of this node's right child returns a non-null value, you should return that.

You need to test for all of these possibilities before you can safely conclude that there's no match in the subtree rooted at this node, and therefore that you can and should return null. In particular, you cannot just blindly return the result of the first recursive call in step 2; if it's null, you need to check step 3 as well.

A simple implementation of the logic I described above would look like this:

public Node getParent(int search, Node position) 
{
    // check for null argument, so the caller doesn't have to
    if (position == null) return null;

    // we'll need these child nodes below
    Node left = position.getLeft(), right = position.getRight();

    // step 1: if either child matches the target, return this node
    if (left != null && left.getContent() == search) return position;
    if (right != null && right.getContent() == search) return position;

    // step 2: recursively check left subtree
    Node leftMatch = getParent(search, left);
    if (leftMatch != null) return leftMatch;

    // step 3: recursively check right subtree
    Node rightMatch = getParent(search, right);
    if (rightMatch != null) return rightMatch;

    // no match
    return null;
}

Of course, step 3 and the "no match" case can be trivially combined into just:

    // step 3: recursively check right subtree, pass whatever it returns to caller
    return getParent(search, right);

but doing so hides the similarity between steps 2 and 3.

---

Ps. In practice, of course, there's rarely if ever any reason to write a full depth-first recursive search like this in the first place. Typically, you would either have your tree arranged so that you can always tell which subtree the target node would be in, if it was present, or, if you really needed to find arbitrary nodes in a tree that was not arranged to make that easy, you would use some kind of an auxiliary data structure (such as a hash table) to let you quickly look up the position of each node in the tree. Also, if you frequently need to find the parent of a specific node, it's usually easiest to just have each node in the tree explicitly store a reference to its parent.

About the only time such a recursive search is commonly needed is when the "tree" you're searching is not actually a real data structure, but rather some conceptual search space (such as the set of possible moves in a game) that just happens to be arranged like a tree. In that case, the shape and order of the search space are determined by the problem you're trying to solve, so you're not actually free to choose a better arrangement for your data.

Answer 3

What you are trying to do is find a Node that has value search

public Node findNode(int search, Node position) {
    /**
     * There is no solution under node 'position'
     */
    if (position == null)
        return null;

    /**
     * Current node is the searched node
     */
    if (position.getContent() == search)
        return position;

    Node fromLeft = findNode(search, position.getLeft());

    if (fromLeft != null)
        return fromLeft;

    /**
     * In case the 'search' value is not on the left, we need to try
     * search to the right.
     */
     return findNode(search, position.getRight());
}