0

I am making a binary tree from given inorder and preorder traversal array and I don't know why it is giving me the wrong output although it works perfectly for some points in the given array

#include<iostream>

using namespace std;

class Node
{
    public:
        int i;
        Node* left;
        Node* right;
        bool isThreaded;
        Node(int j);
};

Node::Node(int j):i(j)
{
    left=NULL;
    right=NULL;
}

void inorder(Node* root)
{
    if(root)
    {
        inorder(root->left);
        cout<<root->i<<"  ";
        inorder(root->right);
    }
}

int findkey(int* a, int l, int r, int key)
{
    for(int i=l; i<r; i++)
    {
        if(a[i]==key)
            return i;
    }

    return -1;
}

Node* ConstructfromPreorderInorder(int* pre, int n, int* in, int l, int  r, int& k)
{
    Node* root=NULL;

    if(k<n && l<r)
    {
        int key=findkey(in, l, r, pre[k]); //Finds the index of current preorder element in inorder array


        root=new Node(pre[k++]); //Forms the node

        root->left=ConstructfromPreorderInorder(pre, n, in, 0, key, k); //To find the left subtree we traverse to left of the index of element in inroder array

        root->right=ConstructfromPreorderInorder(pre, n, in, key+1, r, k);
        //Similarly we traverse right to form right subtree
    }
    return root;
}

int main()
{
    int pre[]={1,2,4,5,3,6,7};
    int in[]={4,2,5,1,6,3,7};

    int n=sizeof(pre)/sizeof(*pre); //Function used to find the no. of elements in an array. In this case elements in preorder array. Both are same so can use any

    int i=0;
    Node* root2=ConstructfromPreorderInorder(pre, n, in, 0, n, i);
    inorder(root2);
}

Although it works for the the half of elements in the array but after that it gives unusual results. I have added print statements for better view.

Please see to it if it helps.

Improve this question
7
  • 1
    Please change your title to something meaningful "my code gives wrong answers" won't help any other user that has the same problem, because it doesn't describe the problem. Commented May 14, 2015 at 17:17
  • I hope that corrects Commented May 14, 2015 at 17:19
  • Could you please add some comments to the code (or even better, change the variable names to meaningfull names rather than letters). Lines like int n=sizeof(pre)/sizeof(*pre); Just aren't trivial enough to decipher without any comments Commented May 14, 2015 at 17:32
  • Also, if you use a print statement, please take the effort of printing something meaningfull between your variables. Not just for yourself, but also for others:) Commented May 14, 2015 at 17:38
  • possible duplicate of How to construct a binary tree using a level order traversal sequence Commented May 14, 2015 at 21:22

2 Answers 2

Reset to default
3

For constructing left subtree range should start from l instead of 0.

root->left=ConstructfromPreorderInorder(pre, n, in, l, key, k);

instead of

root->left=ConstructfromPreorderInorder(pre, n, in, 0, key, k);
Improve this answer
Sign up to request clarification or add additional context in comments.

1 Comment

Thanks. That was a silly mistake, appreciate that U went through such long code. Thanks a lot
0

The answer to your underlying question, "How do I debug this code?":

  • Find the simplest possible fail case.
  • Test parts of the code separately, such as findkey.
  • Step through it in your mind.
  • Step through it in a debugger.
  • Add verbose print statements.

Example of the last:

Node* ConstructfromPreorderInorder(int* pre, int n, int* in, int l, int  r, 
 int& k)
{
cout << "constructing from " << l << " to " << r << " at " << k << endl;
Improve this answer

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.