In order traversal in a BST

general
, , , ,
1

Following is code snippet from geeksforgeeks. Although I understand what this code is doing, however I am struggling understanding from code itself. Can anybody explain it line by line. Thanks.

 bool isBST(struct node* root)
{
static struct node *prev = NULL;
 
// traverse the tree in inorder fashion and keep track of prev node
if (root)
{
    if (!isBST(root->left))
      return false;

    // Allows only distinct valued nodes 
    if (prev != NULL && root->data <= prev->data)
      return false;

    prev = root;

    return isBST(root->right);
}

return true;}
2

The point is that the tree is going to be visited in in-order manner, and prev will always point to a node which was visited before the root, that is to the in-order predcessor of that node. Than it will be checked if that node value is bigger than it’s predcessor value. If that fails once, the function will return false, otherwise tree is BST.

3

Firstly, this code is basically to check whether the given tree is a BST or not. It does not print the inorder traversal of the BST.
The idea behind this is that we store the value of the previous node and compare it with the value of the current node to check if it is smaller or greater. Now how does that help us?

If noticed carefully, in the inorder traversal , a value that appears before has to be smaller than a value that appears later, because the left child is smaller than the root and the root is smaller than the right child and the order we follow to traverse the BST is :

In inorder traversal, we traverse as follows :

  1. left child

  2. root

  3. right child

Now the code :

if (!isBST(root->left))

return false;

The above portion is a recursive call to the function with the left child as argument. If a false value is returned from the left subtree then return false.

if (prev != NULL && root->data <= prev->data)

return false;

This part compares the previous value with the current ( the current is root ) and returns false if current <= previous.
Notice the <= . This is because BST does not allow two nodes with the same value.

prev = root;

The above statement assigns the current value to the previous variable and we go on to the right subtree to check for the condition of BST with the following code :

return isBST(root->right);

This returns the value received from a recursive call to the function with the right child as argument.

That’s it.

One important thing to note here is that the prev variable is made static, meaning, new instances are not created for it with successive calls to the function. It is not redeclared with successive calls to the isBST() function. This is necessary as we require the prev value that we stored earlier before calling the function.

4

static variable is the one which is not destroyed even when a function goes out of scope. so the variable will be assigned NULL initially but from the next time in recursion its value will not change by line 1 of the function definition. It will only change by line prev=root.

root here is the current node worked upon.

now we assume that this is correct ; also we have a 3 level BST with following convention for name of nodes in our minds and dry run this.(sorry i didn’t have karma to upload image of a bst)
1
2 3
4 5 6 7
(note these are just names not the values)

first prev=NULL

Then
if(!BST(root->left))
we enter into next level of iteration and we keep on entering until we reach a leaf and BST.left() becomes null and if(!BST.left()) is called for the leaf since it is null its execution will return True as if(root) condition fails. Now remember that we were at leftmost leaf(4) and prev is still null.

now we check if(prev != NULL && root->data <= prev->data)
but it is false since prev is null and we go to isbst(root-> right) which returns true as it fails at if(root) also prev remains left most leaf(4).and we are one level back due to return and if(!isBST(root->left)) must have return true.

now again execute (prev != NULL && root->data <= prev->data) for 2
here we will compare 2(root) with 4(prev) and prev will become 2

now extending this to right bst; we will be comparing root(5) with prev(2) as expected and ;

so you can see in a lnode parent rnode subsection of binary tree that first prev takes value of left node and compare with parent and then prev takes value of parent to compare with right node as expected.

Pls upvote if you find it useful.
For any querry’s comment/menton me in answer.

1 Like
5

You know what’s better?

use this for inorder traversal

void inorder(struct node *r)
{

inorder(r->left);

printf("%d",r->data);

inorder("%d",r->right);

}
6

@diveshuttam Can you also help me with this:

http://code.geeksforgeeks.org/UILnCa
Function starting with line 29.

1 Like
7

Sorry here is just a short explanation as it will take time to figure out details.I will post the detailed explanation tomm. on your main discuss question(if you don’t get one).
it is an example of inorder traversal ;what the first 2 lines of that function do is get us to the left most element(which is by property smallest) and then we traverse the graph in order(ascending) and keep on incrementing count till it reaches k(kth element) and return that element.
If u have any doubt in inorder traversal watch this https://youtu.be/LvKj_4dJmvM?list=PLRdux5uhMFidXKokCp5A_6ROOD8AkWCLB
Hope it helps.

1 Like
8

@diveshuttam thanks again for replying… and your reply more than sufficed… thanks again…

9

ok great then.