Hi

Can someone please help me figure out how to find the parent of a node? Here is the closest I got to something that works. It finds the parent and prints it out "parent: x" but it doesn't send the parent node back ?

Any help would be appreciated.

BinaryNode Class

private static class BinaryNode<AnyType>
	{
		BinaryNode(AnyType theElement)
		{
			this(theElement, null, null);			
		}
		
		BinaryNode(AnyType theElement, BinaryNode<AnyType> lt, BinaryNode<AnyType> rt )
		{
			element = theElement;
			left = lt;
			right = rt;
		}
		
		AnyType element;
		BinaryNode<AnyType> left; 
		BinaryNode<AnyType> right; 
	}
public BinaryNode<AnyType> getParent(AnyType x)
	{
		BinaryNode<AnyType> aParent = getParent(x, root);
		System.out.println("found :: : " + aParent.element);
		return aParent;
	}
private BinaryNode<AnyType> getParent(AnyType x, BinaryNode<AnyType> t)
	{
		if (t != null)
		{
			if (t.left != null)	
			{				
				if (x.compareTo(t.left.element)==0)
				{
					System.out.println("parent: " + t.element);
					return t;
				}
					
			}
			if (t.right != null)
			{
				if (x.compareTo(t.right.element)==0)
				{
					System.out.println("parent: " + t.element);
					return t;
				}
			}
			getParent(x,t.left);
			getParent(x,t.right);			
		}
return t;
}

Here's an implementation that works, any other sollutions will be appreciated :>

private BinaryNode<AnyType> getParent(AnyType x, BinaryNode<AnyType> t)
	{
		
		if (t == null)
			return null;
		
		
		int compareResult = x.compareTo(t.element);
		
		if (t.left!=null)
			if (x.compareTo(t.left.element) == 0)				
				compareResult =0 ;			
			
		if (t.right!=null)
			if (x.compareTo(t.right.element) == 0)
				compareResult = 0;	
		
				
		
		if (compareResult < 0)
			return getParent(x, t.left);
		else if (compareResult > 0)
			return getParent(x, t.right);
		else
			return t;
	}

Other solution:

private static BinaryNode getParent(AnyType x, BinaryNode<AnyType> t, BinaryNode<AnyType> parent) {
            if (t == null) {
                return null;
            } else {
                if (x.compareTo(t.element) < 0) {
                    return getParent(x, t.left, t);
                } else if (x.compareTo(t.element) > 0) {
                    return getParent(x, t.right, t);
                } else {
                    return parent;
                }
            }
        }

Invoke with parent=null.
Important question. Parent of root. Null or root?

This article has been dead for over six months. Start a new discussion instead.