13,054,615 members (59,000 online)
Rate this:
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.

```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 7:57am

Rate this:

## 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`
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.

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:

## 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.

Top Experts
Last 24hrsThis month
 OriginalGriff 175 Graeme_Grant 168 Jochen Arndt 135 Dave Kreskowiak 85 RickZeeland 60
 OriginalGriff 5,731 RickZeeland 2,014 ppolymorphe 1,858 F-ES Sitecore 1,646 Dave Kreskowiak 1,494