How to get the prev element in an inorder successor in a BST - comparison of two problems

Here think very naively first. You can simply write the inorder traversal of the BST. Now, that would be a sorted array. If two non-adjacent nodes are swapped, then there would be two inflection points in the array. Write a BST, write its inorder traversal and check. Looking at an example you can easily realize that there will be another case where the two adjacent nodes will be swapped. So in that case there will be two inflection points. Now this solution will take O(n) extra space.

However, you can do it easily using recursion. Think about it. First what do you need to think ? How to traverse the tree. Here, you need to compare the previously seen element with the current element. So, if the previous is in the left subtree, the root can be the current. Its a typical case of inorder traversal and is similar to Convert a BST to a double linked list problem.

 We will maintain three pointers, first, middle and last. When we find the first point where current node value is smaller than previous node value, we update the first with the previous node & middle with the current node. When we find the second point where current node value is smaller than previous node value, we update the last with the current node. In case #2, we will never find the second point. So, last pointer will not be updated. After processing, if the last node value is null, then two swapped nodes of BST are adjacent

void correctBSTUtil( struct node* root, struct node** first,

                     struct node** middle, struct node** last,

                     struct node** prev )

{

    if( root )

    {

        // Recur for the left subtree

        correctBSTUtil( root->left, first, middle, last, prev );

 

        // If this node is smaller than the previous node, it's violating

        // the BST rule.

        if (*prev && root->data < (*prev)->data)

        {

            // If this is first violation, mark these two nodes as

            // 'first' and 'middle'

            if ( !*first )

            {

                *first = *prev;

                *middle = root;

            }

 

            // If this is second violation, mark this node as last

            else

                *last = root;

        }

 

        // Mark this node as previous

        *prev = root;

 

        // Recur for the right subtree

        correctBSTUtil( root->right, first, middle, last, prev );

    }

}

 

Look at the way prev is stored here. We just store the root which is the previously seen element. You can get a clear understanding of how this thing can be altered in another problem. Looking at these two problems will improve your clarity of thinking. The problem is Convert a BST to doubly linked list

 

void treeToDoublyList(Node *p, Node *& prev, Node *& head) {

  if (!p) return;

  treeToDoublyList(p->left, prev, head);

  // current node's left points to previous node

  p->left = prev;

  if (prev)

    prev->right = p;  // previous node's right points to current node

  else

    head = p; // current node (smallest element) is head of

              // the list if previous node is not available

              //because prev will come from left subtree in the recursion. There is no left subtree, so it the smallest and head

  // as soon as the recursion ends, the head's left pointer

  // points to the last node, and the last node's right pointer

  // points to the head pointer.

  Node *right = p->right;

  head->left = p;

  p->right = head;

  // updates previous node

  prev = p; // In an inorder traversal before going to the right subtree the previous always gets updated

  treeToDoublyList(right, prev, head);

}

 

 

// In an inorder traversal before going to the right subtree the previous always gets updated