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;
}``````

All 2 Replies

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?

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.