Geek asks and answers

In BST, two nodes are randomly swapped, we need to find these two nodes and swap them back

A binary search tree is specified in which any two nodes are replaced. Therefore, we need to find these two nodes and swap them back (we need to swap, not the data)

I tried to do this by creating an additional array that has a traversal inside the tree, and also stores a pointer to each node. Then we just go through the array and find two nodes that are not in sorted order, now these two nodes are searched in the tree and then replaced

So my question is how to solve this problem in O (1) space?

+5
source share
3 answers

BST , .
, ( ) .

, " ", .

, , , O(1), O(h), h - - . , O(logn)

+7

BST O (1).

, , , nonRecrusiveInOrderTraversal Wikipedia Tree_traversal.

, BST , , ( , node).

/ , .

, , , . ( , ).

0

We can change the isBST () method as shown below to swap these 2 randomly changed nodes and fix them.

/* Returns true if the given tree is a binary search tree
 (efficient version). */
int isBST(struct node* node)
{
  struct node *x = NULL;
  return(isBSTUtil(node, INT_MIN, INT_MAX,&x));
}

/* Returns true if the given tree is a BST and its
   values are >= min and <= max. */
int isBSTUtil(struct node* node, int min, int max, struct node **x)
{

  /* an empty tree is BST */
  if (node==NULL)
     return 1;

  /* false if this node violates the min/max constraint */
  if (node->data < min || node->data > max) {
     if (*x == NULL) {
        *x = node;//same the first incident where BST property is not followed.
     }
     else {
        //here we second node, so swap it with *x.
        int tmp = node->data;
        node->data = (*x)->data;
        (*x)->data = tmp;

     }
     //return 0;
     return 1;//have to return 1; as we are not checking here if tree is BST, as we know it is not BST, and we are correcting it.
  }
  /* otherwise check the subtrees recursively,
   tightening the min or max constraint */
  return
    isBSTUtil(node->left, min, node->data-1, x) &&  // Allow only distinct values
    isBSTUtil(node->right, node->data+1, max, x);  // Allow only distinct values
}
0
source

More articles:


All Articles