Find swapped nodes in a BST

Question

0.00/5 (No votes)

See more:

I am trying to write a program that can detect and print two nodes in BST that have been swapped.

In a three level tree, I reached near to the solution using this approach.

C++

If (!AllSubTreeAreValid())
{
//Nodes swapped on same side of main root node
}
else
{
  int max = getMax(root->left);
  int min = getMin(root->right);
  if(max > root->data || min < root->data )
  {
     //Nodes swapped on different sides of main root node
     //Print max and min values

  }
else 
{
 //No node swappped
}
}

//Helper functions
int GetMaxEle(TreeNode* tree)
{
    while(tree->right!=NULL)
    {
        tree=tree->right;
    }
    return tree->info;
}

int GetMinEle(TreeNode* tree)
{
    while(tree->left!=NULL)
    {
        tree=tree->left;
    }
    return tree->info;
}

but the above approach failed when I tried to test with four level tree.

C++

             20

      15            30

   10    17       25     33

9  16  12  18  22  26  31  34

Being in root node 15's right subtree, 12 is still greater (violation).

Being in root node 15's left subtree, 16 is still greater (violation).

So, 16, 12 are the swapped elements in the above BST. How do I find them through the program?

Posted 31-Aug-11 7:57am

optimus_prime1

Add a Solution

2 solutions

Add a Solution

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

dasblinkenlight · Answer 1 · 2011-08-31T09:57:00

Solution 1

Convert the tree to a list using an in-order traversal[^]. The list will be sorted, except for the two swapped elements. The first of them will be followed by a smaller number; the second one will be preceded by a larger number.

9 10 16 <- next number is smaller 15 12 <- prior number is larger 17 18 20 22 25 26 30 31 33 34

Posted 31-Aug-11 9:57am

dasblinkenlight

Comments

optimus_prime1 1-Sep-11 0:54am

This proves to be the wrong approach. Consider these elements in the list after traversal: 2, 7, 5, 10, 12, 15, 17

5, 7 are consecutive and not working according to above approach.

dasblinkenlight 1-Sep-11 8:40am

It's of no consequence that they happen to be consecutive: seven is still followed by a smaller number (five), and five is still preceded by a larger number (seven).

mbue · Answer 2 · 2011-08-31T16:37:00

Nice game:

C++

#pragma once
#include <stdio.h>
#include <tchar.h>

class TreeNode;
class vWalkTree
{
public: // vWalkTree
  virtual  int  Enter(TreeNode* p) = 0;
  virtual  int  Leave(TreeNode* p) = 0;
};

class TreeNode
{
public:
  TreeNode(const int v,TreeNode* l=0,TreeNode* r=0){ value=v; left=l; right=r; }
  ~TreeNode(){ if(left) delete left; if(right) delete right; }

  int        get(){ return value; }

  TreeNode*  most_left();
  TreeNode*  most_right();
  int        compare(TreeNode* with){ return value-with->value; }
  void      swap(TreeNode* p){ int v=value; value=p->value;  p->value=v; }
  void      walk(vWalkTree& w);

private:
  TreeNode*  left;
  TreeNode*  right;
  int        value;
};

void TreeNode::walk(vWalkTree& w)
{
  if(w.Enter(this))
  {
    if(left) left->walk(w);
    if(right) right->walk(w);
    w.Leave(this);
  }
}

TreeNode*  TreeNode::most_left()
{
  TreeNode* r;
  TreeNode* l;
  l = left  ? left ->most_right():0;
  if(l && (0>compare(l))) swap(l);
  r = right ? right->most_left ():0;
  if(r && (0<compare(r))) swap(r);
  return left?left->most_left():this;
}

TreeNode*  TreeNode::most_right()
{
  TreeNode* r;
  TreeNode* l;
  l = left  ? left ->most_right():0;
  if(l && (0>compare(l))) swap(l);
  r = right ? right->most_left ():0;
  if(r && (0<compare(r))) swap(r);
  return right?right->most_right():this;
}

int _tmain(int argc, _TCHAR* argv[])
{
  /*
             20
 
      15            30
 
   10    17       25     33
 
9  16  12  18  22  26  31  34
  */
  TreeNode  root
  (
    20,
    new TreeNode
    (
      15,
      new TreeNode(10,new TreeNode(9),new TreeNode(16)),
      new TreeNode(17,new TreeNode(12),new TreeNode(18))
    ),
    new TreeNode
    (
      30,
      new TreeNode(25,new TreeNode(22),new TreeNode(26)),
      new TreeNode(33,new TreeNode(31),new TreeNode(34))
    )
  );
  
  class PrintTree : public vWalkTree
  {
  public: // vWalkTree
    int    Enter(TreeNode* p)
    {
      if(reached==level){ ++done; _tprintf(__T("%i "),p->get()); }
      ++reached;
      return 1;
    }
    int  Leave(TreeNode* p)
    {
      --reached;
      return 1;
    }
    PrintTree(){ level=0; reached=0; done=0; }
  public:
    unsigned int  level;
    unsigned int  done;
  private:
    unsigned int  reached;
  };

  PrintTree  walk;
  _tprintf(__T("--- before ---\r\n"));
  walk.level = 0;
  do{ walk.done=0; root.walk(walk); ++walk.level; _tprintf(__T("\r\n")); }while(walk.done);
  root.most_left();
  _tprintf(__T("--- after ---\r\n"));
  walk.level = 0;
  do{ walk.done=0; root.walk(walk); ++walk.level; _tprintf(__T("\r\n")); }while(walk.done);
  _gettch();
  return 0;
}

Regards.

Find swapped nodes in a BST

2 solutions

Solution 1

Solution 2

Add your solution here

Preview 0

Find swapped nodes in a BST

2 solutions

Solution 1

Solution 2

Add your solution here

Preview 0

Existing Members

...or Join us