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

Add your solution here

Treat my content as plain text, not as HTML

Preview 0

…

Existing Members

Sign in to your account

...or Join us

Download, Vote, Comment, Publish.

Your Email
Password
Forgot your password?

Your Email
This email is in use. Do you need your password?
Optional Password

I have read and agree to the Terms of Service and Privacy Policy
Please subscribe me to the CodeProject newsletters

When answering a question please:

Read the question carefully.
Understand that English isn't everyone's first language so be lenient of bad spelling and grammar.
If a question is poorly phrased then either ask for clarification, ignore it, or edit the question and fix the problem. Insults are not welcome.
Don't tell someone to read the manual. Chances are they have and don't get it. Provide an answer or move on to the next question.

Let's work to help developers, not make them feel stupid.

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.