Find the parent node of a node in binary search tree

Question

So I want to find the parent node of a Node in a binary tree. Suppose that I input 30,15,17,45,69,80,7 in the tree through a text file.

The tree should be

                 30
             15       45
          7      17       69
                               80

And here is my code :

Node*  BST::searchforparentnode(Node* pRoot, int value)
{
   if(pRoot->pleft == NULL && pRoot->pright == NULL)
    return NULL;

   if(pRoot->pleft->value == value || pRoot->pright->value == value)
    return pRoot;

   if(pRoot->value > value)
    return searchforparentnode(pRoot->pleft,value);

   if(pRoot->value < value)
    return searchforparentnode(pRoot->pright,value);

}

In this case i'm not consider if the user input the value of the Root node.

Thing is, when I input 15,17,7, all the value in the left branch of Root node, it came out ok. But when i want to find parent Node of the values from the right branch (69,80) EXCEPT for 45, the program stop running.

Any idea about what caused this error guys? Thanks for reading.

Answer 1

It appears that 45 does not have a left node, it is NULL, so checking pRoot->pleft->value == value is undefined behavior.

             30
            /  \
         15     45
        /   \     \
      7      17    69
                     \
                      80

So you need to do a check, something like:

Node*  BST::searchforparentnode(Node* pRoot, int value)
{
    if(pRoot->pleft == NULL && pRoot->pright == NULL)
       return NULL;

    if( (pRoot->pleft != NULL && pRoot->pleft->value == value)
        || (pRoot->pright != NULL && pRoot->pright->value == value))
       return pRoot;

    if(pRoot->value > value)
       return searchforparentnode(pRoot->pleft,value);

    if(pRoot->value < value)
       return searchforparentnode(pRoot->pright,value);
}

However, another thing to check for is if pRoot itself is NULL:

Node*  BST::searchforparentnode(Node* pRoot, int value)
{
    if (pRoot == NULL)
       return NULL;

    if(pRoot->pleft == NULL && pRoot->pright == NULL)
       return NULL;

    if( (pRoot->pleft != NULL && pRoot->pleft->value == value)
        || (pRoot->pright != NULL && pRoot->pright->value == value))
       return pRoot;

    if(pRoot->value > value)
       return searchforparentnode(pRoot->pleft,value);

    if(pRoot->value < value)
       return searchforparentnode(pRoot->pright,value);
}

Answer 2

Your Problem is:

if(pRoot->pleft->value == value || pRoot->pright->value == value)

because before you checked if left AND right is null. In the section mentioned above, one could be null

You maybe wanna Change your code to something like this:

Node*  BST::searchforparentnode(Node* pRoot, int value)
{
   if(pRoot->pleft == NULL && pRoot->pright == NULL)
    return NULL;

   //Added check 
   if(pRoot->pleft && pRoot->pleft->value == value)
    return pRoot;

   //Added check
   if(pRoot->pright && pRoot->pright->value == value)
    return pRoot;

   //Check also needed here
   if(pRoot->pleft && pRoot->value > value)
    return searchforparentnode(pRoot->pleft,value);

   //Check also needed here
   if(pRoot->pright && pRoot->value < value)
    return searchforparentnode(pRoot->pright,value);

}

IMHO: You could also create a pointer to the parent node in each node. This could Speed up certain things a lot!

Answer 3

The following code snippet should do the trick:

public Node parent(Node root, int childValue){
  if(root == null)
    return null;
  Node left = root.left;
  Node right = root.right;
  if(left != null && left.value == childValue)
    return root;
  else if(right != null && right.value == childValue)
    return root;
  else if(left != null && left.value > childValue)
    return parent(left, childValue);
  else if(right != null && right.value < childValue)
    return parent(right, childValue);
   else
     return null;
 }

Answer 4

You can also write simple iterative version of this subroutine as follows:

public Node parent(Node root, int childValue){
  Node parent = NULL;
  while(root != NULL && root.value != childValue) {
       parent=root;
       if(root.value > childValue)
         root = root.left;
       else
         root=root.right;
  }
  return parent

Answer 5

public Node nodeParent(Node root, Node n){
        if(root==null){
            return null;
        }
        Node p=root;
        if(p.left==null && p.right==null ){
            return null;
        }
        if(p.left!=null && p.key>n.key){
            p=p.left;
            if(p.left.key==n.key){
            return p;
        }
        }
        if(p.right!=null && p.key<n.key){
            p=p.right;
            if(p.right.key==n.key){
            return p;
        }
        }
        if(p.left!=null && p.right!=null ){
            if(p.key<n.key){
                p=p.right;
            }else{
                p=p.left;
            }
        }
        return p;
    }