Find Parent of a given node value in Binary Tree

Question:

Given a binary tree node and root node, get the parent node of that node.

Solution:

Solution is very simple.

Before we go to the child node of any parent node, we check if the children nodes is equal to given value.

If it is equal, then we return that node. Else we recursively call the left and right child and perform similar actions.

Solution in C++

#include <iostream>
#include <queue>
#include <stack>
using namespace std;

// structure to hold binary tree node
struct Node
{
    int data;
    Node *left, *right;

    Node(int data)
    {
        this->data = data;
        this->left = this->right = nullptr;
    }
};

void get_parent(Node* node, int val, int parent) 
{ 
    if (node == NULL) 
        return; 
  
    if (node->data == val) 
    { 
          cout << "The parent of node "<<val<< " is = "<< parent<<endl; 
    } 
    else 
    { 
        get_parent(node->left, val, node->data); 
        get_parent(node->right, val, node->data); 
    } 
} 

int main()  
{  
    Node* root = nullptr;
    /* Binary tree:
              16
            /   \
           /     \
          10      25
         /  \    /  \
        /    \  /    \
       7    15 18     30

    */

    root = new Node(16);
    root->left = new Node(10);
    root->right = new Node(25);
    root->left->left = new Node(7);
    root->left->right = new Node(15);
    root->right->left = new Node(18);
    root->right->right = new Node(30);

    get_parent(root, 15, -1);




    return 0;  
}  

Output:

The parent of node 15 is = 10