Click here to Skip to main content
16,004,453 members
Please Sign up or sign in to vote.
0.00/5 (No votes)
See more:
it must say if question1 is an ancestor of question2 in a binary tree

#include <iostream>
#include <string>
using namespace std;

struct node
{
    string question;
    node *left, *right;


};



node *newNode(string m_question)
{
    node *temp=new node;
    temp->question=m_question;
    temp->left=NULL;
    temp->right=NULL;
    return temp;
}





bool is_ancestor(node* start, string question1, string question2)
{
    node *root;

    if(start==NULL){return false;}
    if(start->question==question1)
    {

        while(start!=NULL)
        {
            if(start->left->question==question2)
            {
                return true;

            }
            else{
                start=start->left;
            }

        }
        while(root!=NULL)
        {
            if(root->right->question==question2)
            {
                return true;
            }
            else{
                root=root->right;
            }
        }
    }
    else{
        is_ancestor(start->left, question1, question2);
        is_ancestor(start->right, question1, question2);
    }
}
int main() {

    node *start = newNode("Bob");

    node *root=start;

    string question1="Jack";
    string question2="Linda";

    start->left = newNode("Jack");
    start->right = newNode("Maria");



    start->left->left = newNode("Linda");

    cout<<is_ancestor(start, question1, question2)<<endl;
}
C++



What I have tried:

I have tried to solve by two nodes pointing to the first node(start and root). when I debug, I see that after return true statement it goes inside else block and recursively traverses binary tree again. why is it like that?
Posted
Updated 28-Nov-17 0:28am

1 solution

Your binary tree search procedure is faulty. The 'canonical' binary tree search procedure works like this:

BinarySearch(TreeNode* currentNode)

1. If currentNode is NULL, return failure.
2. If currentNode is the one that you want, return success.
3. If BinarySearch(currentNode->left) succeeded, return success.
4. Return BinarySearch(currentNode->right)

Now think. In order for 'question1' to be an ancestor of 'question2', what conditions must be true?
 
Share this answer
 
Comments
Member 13277493 30-Nov-17 11:34am    
Thanks for helping. I must find question1 and traverse the left and right subtrees to find question2. yes?

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)



CodeProject, 20 Bay Street, 11th Floor Toronto, Ontario, Canada M5J 2N8 +1 (416) 849-8900