How to create a method that gets the previous node using a Binary Search Tree in Java?

Question

I am working on a method that gets the previous node using a binary search tree. Now I think I got this, however I am struggling with my if statements.

The instructions are the getPrevNode(BSTNode) method should find the node in the tree that comes before the parameter. And here is the algorithm that I am working with.

• If the node has a left child, move down the left subtree to get the max node

• Otherwise, if the node has a parent, we'll need to move up the tree as follows:

• If the node is a right child, return its parent

• If the node is a left child, move up the tree until you are a right child and return its parent

• If you reach the root and are never a right child, then there is no previous node

Lets note that this is also a helper method. Therefore, here is my code that I have so far, following that algorithm.

 private BSTNode<E> getPrevNode(BSTNode<E> node)
{
    if(node.left != null)
    {
        return getPrevNode(node.left);
    }
    else if(node.parent != null)
    {
        if(node == node.right)
        {
            return node.parent;
        }
        else if(node == node.left)
        {
            return node.parent;
        }
    }
    return getPrevNode(node);
}

Now I know it's not accurate, but that's why I am asking. I will try to give out some information on this code but I will leave some methods out since I don't want it to be long.

public class BinarySearchTree<E extends Comparable<E>>
{
private BSTNode<E> root; // root of overall tree
private int numElements;
private BSTNode<E> first;
// post: constructs an empty search tree
public BinarySearchTree()
{
    this.root = null;
    this.numElements = 0;
}
private BSTNode<E> getPrevNode(BSTNode<E> node)
{
    if(node.left != null)
    {
        return getPrevNode(node.left);
    }
    else if(node.parent != null)
    {
        if(node == node.right)
        {
            return node.parent;
        }
        else if(node == node.left)
        {
            return node.parent;
        }
    }
    return getPrevNode(node);
}
 public class Iterator
{
    private BSTNode<E> currentNode;

    public Iterator()
    {
        currentNode = first;
    }

    public boolean hasNext()
    {
        return currentNode != null;
    }

    public E next()
    {
        E value = currentNode.data;
        currentNode = currentNode.next;
        return value;
    }
}
private static class BSTNode<E>
{
    public E data;
    public BSTNode<E> left;
    public BSTNode<E> right;
    public BSTNode<E> parent;
    public BSTNode<E> next;

    public BSTNode(E data)
    {
        this(data, null, null, null, null);
    }

    public BSTNode(E data, BSTNode<E> left, BSTNode<E> right, BSTNode<E> parent, BSTNode<E> next)
    {
        this.data = data;
        this.left = left;
        this.right = right;
        this.parent = parent;
        this.next = next;
    }
 }
}

I hope this information is useful.

Answer 1

Try this maybe:

private BSTNode<E> getPrevNode(BSTNode<E> node) {

    if(node.left != null) {
        node = node.left;
        while(node.right != null) {
            node = node.right;
        }
        return node;
    } else if(node.parent != null) {

        // If the node is a right child, return its parent
        if(node.parent.right == node) {
            return node.parent;
        }

        // If the node is a left child, move up the tree 
        // until you are a right child and return its parent
        if(node.parent.left == node) {

            while(node.parent.right != node) {

                // If you reach the root and are never a right child, no previous node return null
                if(node.parent == root) {
                    return null;
                }
                node = node.parent; 
            }
            return node.parent;

        }           
    }

    return null;
}