BST - Binary search Tree

Hi,

Write C++ program to check if a given binary tree is a binary search tree or not?

suggestions:
-------------

If the given binary tree is a Binary search tree, then the inorder traversal should output the elements in increasing order. We make use of this property of inorder traversal to check whether the given binary tree is a BST or not.

The problem here , if I print or insert the nodes according to InOrder Traversal to a buffer , then I can check the values by comparisons, and this final step will increase the complixity of the solution.

How can I do that in lower complixity, I mean without allocating a new buffer and traverse it.??

Thank you

You don't need to insert the nodes into a buffer.
Run the in-order traverse, and verify that each traversed node value is greater or equal to the node traversed just before it.
Note that in in-order traverse, the left sub-tree is traversed, then the current node and then the right sub-tree - the first time you "reach" a node is usually not the same occasion it is traversed, you just pass through it (unless, of course it's a leaf or it doesn't have a left child).

This method only takes one variable - used to save the value of the last traversed node.

Regards,
Zachm

Thank you Zach always :-) seems that you are the only one who helps me here , hope that you can help me always to understand things that I rarly use...

I have few things that need explanation more.
Lets say that the code is as following:

void inorder_print(tree T)
{
if (T!=NULL)
{
inorder_print(T->left);
printf("%d\n",T->data);
inorder_print(T->right);
}
}


The question here , how to verify that each traversed node value is greater or equal to the node traversed just before it.?

what code you have to add to my method in order to do that ??

One more thing.. can I have your email or MSN so i can talk to you faster if you do not mind?? :-)

I need to ask you few things about the recursion execution order here also ...

Imagine that our tree look slike:


60

30 80

10 40 70 9


when processing or applying InOrder , we go from 60 to 30 to 10 -->Null (left), then we go to the next statement and print 10, and then go to the right, and we get Null, and return back to 30.. right?? It is stack fram...

as I know that 30 should be printed... InOrder traversal

Now the question is how is it done??
As I understand, when we go back to 30, the InOrder function will get 30, and start to execute again, the first statement is processin the left.. what makes the function does not go to the left again ?? or to the print , but goes to teh right??

Thank you always... and sorry again

Wael





wael

Quote:

---

Originally Posted by wael.salman

The question here , how to verify that each traversed node value is greater or equal to the node traversed just before it.?

what code you have to add to my method in order to do that ??

---

Just keep the last "printed" node in a variable. I'm not sure what language you use, in C++ I would do:

Code:

---

#include <iostream>

struct TreeNode
{
        int value;
        TreeNode* left;
        TreeNode* right;
};

class BSTChecker
{
public:
        BSTChecker(TreeNode& root)
        {
                m_Root = &root;
                m_LastTraversedNode = NULL;
        }

        bool isBinarySearchTree()
        {
                m_LastTraversedNode = NULL;
                return isBinarySearchTreeRecursive(m_Root);
        }

private:
        bool isBinarySearchTreeRecursive(TreeNode* node)
        {
                bool isBST = true;
                if (node != NULL)
                {             
                        isBST = isBinarySearchTreeRecursive(node->left);
                        isBST = isBST  &&
                                  (m_LastTraversedNode == NULL || m_LastTraversedNode->value <= node->value);
                        m_LastTraversedNode = node;
                        isBST = isBST && isBinarySearchTreeRecursive(node->right);
                }

                return isBST;
        }

        TreeNode* m_LastTraversedNode;
        TreeNode* m_Root;
};


int main()
{
        TreeNode a, b, c, d, e;
        a.left = &b;
        a.right = &c;
        b.left = &d;
        b.right = &e;
        a.value = 10;
        b.value = 5;
        c.value = 15;
        d.value = 3;
        e.value = 7;
        c.left = c.right = NULL;
        d.left = d.right = NULL;
        e.left = e.right = NULL;

        BSTChecker checker(a);
        bool isBst = checker.isBinarySearchTree();

        if (isBst)
        {
                std::cout << "It's a BST !\n";
        }
        else
        {
                std::cout << "It's not a BST !\n";
        }
        std::cin.get();
}

---

Quote:

---

Originally Posted by wael.salman

One more thing.. can I have your email or MSN so i can talk to you faster if you do not mind?? :-)

---

I will not post any personal details on any forum pages - this is a recipe for getting a lot of spam. PM me if you need anything, if I have some time I will try to help.

Quote:

---

Originally Posted by wael.salman

when processing or applying InOrder , we go from 60 to 30 to 10 -->Null (left), then we go to the next statement and print 10, and then go to the right, and we get Null, and return back to 30.. right?? It is stack fram...

as I know that 30 should be printed... InOrder traversal

Now the question is how is it done??
As I understand, when we go back to 30, the InOrder function will get 30, and start to execute again, the first statement is processin the left.. what makes the function does not go to the left again ?? or to the print , but goes to teh right??

---

Each recursive function call means that the current code position is pushed to the stack, as well as other function scope data, and the same code position is returned to when the recursive call is finished, so if you made a function call at this line(marked in red):

Code:

---

void inorder_print(tree* T)
{
    if (T!=NULL)
    {
      inorder_print(T->left);
        printf("%d\n",T->data);
        inorder_print(T->right);
    }
}

---

When the function finishes, the code position will be pop'ed from the runtime stack and it will point to the next line -
printf("%d\n",T->data);

So, your understanding was wrong - the function doesn't start from the beginning when an inside function commits. Think about non-recursive nested function - do you expect that the calling function will start from it's beginning once the nested function commits ?

Regards,
Zachm

Hi Zachm,

Thank you so much for your help. I appreciate that . The code is great, but I still have few things unclear about the recursive execution order.

You said:
1. When the function finishes, the code position will be pop'ed from the runtime stack and it will point to the next line -
printf("%d\n",T->data);

I guess that I understand this, but what do u mean by code position?? Lets say that
inorder_print(T->left); is done in line 10 for example, so every time the call is poped up from the stack , it returns to line 10 untill it is done and then continues to the next line
printf("%d\n",T->data);??




2.you also said:
The function doesn't start from the beginning when an inside function commits.

Actually this is not clear for me so much. Lets talk about the last statement to execute , I mean
inorder_print(T->right);

Imagine that the left recursive call was finished , so the first time the call is poped up from the stack, the execution goes to printf ( printing the last left leaf), right?? now, and after that it arrives to the right recursive call. Thjis checks the right of the last left leaf, right?? and lets say it is NULL, so the right call is terminated- committed. what happens next??

Does the execution statemnt pointer - position goes back to the printf statement directly? or starts again from the begining checking if tree!null, and then left , and then printf , and then right??


Actually, I was googling alot to find explanations about nested recursive call order , and did not find, so i believe that this is my chance to have the honer to study something unclear for me from you :-)

Thank you
Wael

consider this code:

Code:

---

1  void nestedFunc1()
2  {
3    //...do something
4  }
5
6  void nestedFunc2()
7  {
8    //...do something else
9  }
10
11 void func()
12 {
13  nestedFunc1();
14  nestedFunc2();
15 }
16
17  int main()
18  {
19    func();
20  }

---

There is no recursion here as you can see. func() calls nestedFunc1() and nestedFunc2(). What I meant was that once nestedFunc1() commits, the code will continue to run from line 14, and won't run line 13 again. This will be the same if the function call was recursive.

Quote:

---

Does the execution statemnt pointer - position goes back to the printf statement directly? or starts again from the begining checking if tree!null, and then left , and then printf , and then right??

---

No, actually the next code line can be either 6, 8 or line 14 from the example code below:

Code:

---

1  void inorder_print(tree* T)
2  {
3      if (T!=NULL)
4      {
5          inorder_print(T->left);
6          printf("%d\n",T->data);
7          inorder_print(T->right);
8      }
9  }
10
11 int main()
12 {
13      inorder_print(tree); //assume 'tree' is defined somewhere else.
14      printf("Finished!");
15 }

---

You can't be sure from which point the function is called, unless you view the function call stack at any given moment.
It's the same as if at the 1st example you would have 3 calls to nestedFunc1(), made from func() - and ask what is the next code line after nestedFunc1() commits - it can be either one of 3 places inside func().

If you want to google anything, google just "recursion" - you'll get tons of resources and examples.

Regards,
Zachm

Thank you very much. Actually i took your code , compiled and viewed the call stack. Now I understand better :-)

There is more few threads opened for me , if you would like to take a look.

Thanx