Click here to Skip to main content
Rate this: bad
good
Please Sign up or sign in to vote.
See more: C++ Algorithms Trees
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.
 
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.
             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 8:57am
Rate this: bad
good
Please Sign up or sign in to vote.

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
  Permalink  
Comments
optimus_prime1 at 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 at 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).
Rate this: bad
good
Please Sign up or sign in to vote.

Solution 2

Nice game:
#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.
  Permalink  

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

  Print Answers RSS
0 OriginalGriff 240
1 Kamal Rocks 184
2 BillWoodruff 173
3 PIEBALDconsult 160
4 CPallini 155
0 OriginalGriff 5,695
1 DamithSL 4,506
2 Maciej Los 4,007
3 Kornfeld Eliyahu Peter 3,480
4 Sergey Alexandrovich Kryukov 3,180


Advertise | Privacy | Mobile
Web04 | 2.8.141216.1 | Last Updated 31 Aug 2011
Copyright © CodeProject, 1999-2014
All Rights Reserved. Terms of Service
Layout: fixed | fluid

CodeProject, 503-250 Ferrand Drive Toronto Ontario, M3C 3G8 Canada +1 416-849-8900 x 100