0

I have a Java task where I have to create a splay tree which requires me to find the parent and grandparent node of the node I am accessing. To do this, I've chosen to create a findParent method. Here is my Node class.

public class Node<T>
{
public T elem = null;
public Node<T> left = null;
public Node<T> right = null;

public Node(T elem) {
    this.elem = elem;
}

public String toString() {
    String out = elem.toString();
    out += " [L: "+ (left == null ? "null" : left.elem) + "] ";
    out += " [R: "+ (right == null ? "null" : right.elem) + "] ";
    return out;
    }
}

I am not allowed to change the Node class. My SplayTree class is made up of these nodes and inside the SplayTree class, I have my findParent function.

public Node<T> findParent(Node<T> A) {
    Node<T> P = root;
    if (P.left == A || P.right == A) {
        return P;
    } else if (A.elem.compareTo(P.elem) < 0) {
        P = P.left;
    } else {
        P = P.right;
    }
    return null;
}

To test the code, I've entered the following numbers in order into the tree "50, 25, 100, 5, 110, 115, 75, 42, 101, 112". The insert method follows the normal BST insert rules of having larger elements on the right and smaller elements on the left. I tested my findParent method using the node containing 110 as the target so theoretically, it should return 100 as the parent and to get the grandparent, I would use findParent(parent) which should return 50 but instead, I get a nullptr exception. I've tested my insert function to see if I am populating my tree correctly, however, that is not the case as the insert method works correctly.

Ying6707
  • 1
  • Which line gives you a null pointer error, please edit your question to include the full error. Also, I don't know what `root` is in your code, but consider what happens when you try to use `P = P.left;` on a `Node` that you have not previously set the value of `left`, it will mean that you are setting P to be null, and if you were to try and reference to it later then you may have difficulty. This is a perfect time to do some debugging using `System.out.println(...);` to check what the values are before you assign them so that you can work out why/where your code is breaking. – sorifiend May 04 '21 at 23:17

1 Answers1

0

you can do it recursively but it may crashes the executing thread with StackOverFlow exception on large data sets

public Node<T> findParent(Node<T> node, Node<T> n){
    if(node == null) return null;
    if(node.right == n || node.left == n){
        return node;
    }else{
        Node<T> r = findParent(node.left, n);
        if(r == null){
            r = findParent(node.right, n);
        }
        return r;
    }
}

public Node<T> findParent(Node<T> n){
    if(n == null)
        throw new NullPointerException("arg0 cannot be Null");
    return findParent(root, n);
}

for large data sets you should have some sort of Stack machine to traverse all the nodes:

public Node<Object> findParent(Node<T> root, Node<T> node){

    Stack<Node<T>> stack = new Stack<>();
    
    stack.push(root);
    
    while(stack.size() > 0){
        Node<T> p = stack.pop();
        if(p.right == node || p.left == node){
            return p;
        }else{
            if(p.left != null){
                stack.push(p.left);
            }else if(p.right != null){
                stack.push(p.right);
            }else{

                
                Node<T> parent = null;
                if(stack.size() > 0)
                    parent = stack.peek();
                
                if(parent == null){
                    break;
                }else if(parent.left == p){
                    if(parent.right != null){
                        stack.push(parent.right);
                    }
                }else if(parent.right == p){
                    stack.pop();
                }
            }
        }
    }

    return null;
}

both tested with your data structure.

in the second example at line 10, if you return the Stack<Node> you can have all the parents in a row

user3840019
  • 155
  • 1
  • 10