Question

c++ Binary Search Tree: find parent of a node please insert comment to explain what the code do. Use struct Node{ int data; Node* left; Node* right};

Answer 1

BST: -

     1
   /   \
  2     3
 / \
4   5

#include<bits/stdc++.h>
using namespace std;
 
/*Binary Search Tree having data with two pointers, i.e., left and right*/
struct Node{
    int data;
    struct Node *left, *right;
    
    Node(int data) {    //constructor to initialize a node
        this->data = data;
        left = right = NULL;
    }
};
 
//function to find  parent of a given node recursively
void findParentNode(struct Node* node, int value, int parent){
    if (node == NULL)           //if tree is empty, the return
        return;
    
 
    //If found the given node
    if (node->data == value){
        if(parent == -1){
                cout<<"Given node has no parent."<<endl;    //if given node has no parent
                }
                else
                cout<<"Parent of given node "<<value<<" is "<<parent<<endl;               //display the parent node
    }
    
    else{
        //Recursively look for the node in left subtree and right subtree
        findParentNode(node->left, value, node->data);
        findParentNode(node->right, value, node->data);
    }
}
 

int main(){
    struct Node* root = new Node(1);
    root->left = new Node(2);
    root->right = new Node(3);
    root->left->left = new Node(4);
    root->left->right = new Node(5);
    
    
    int node;           //user input
    cout<<"Enter the node: ";
    cin>>node;
    cout<<endl;
 
    findParentNode(root, node, -1);
    return 0;
}

Sample Run: -

The program finds recursively finds the given node in the binary search tree. Each time, the head pointer(Node* node) and parent node data is re-assigned to keep track. To check for the given node, there's an if condition. When it's true, it displays the current node's parent stored by variable parent.