Recover Binary Search Tree

Two elements of a binary search tree (BST) are swapped by mistake.

Recover the tree without changing its structure.

C++:
01 void treeWalk(TreeNode* root, TreeNode*& prv, TreeNode*& first, TreeNode*& second)
02  {
03      if(root==NULL)
04         return;
05      treeWalk(root->left,prv,first,second);
06      if((prv!=NULL)&&(prv->val>root->val)){
07          if(first==NULL)
08             first=prv;
09           second=root;
10      }
11      prv=root;
12      treeWalk(root->right,prv,first,second);
13  }
14 
15 void recoverTree(TreeNode *root)
16 {
17      TreeNode* first=NULL;
18      TreeNode* second=NULL;
19      TreeNode* prv=NULL;
20      treeWalk(root,prv,first,second);
21      int tmp=first->val;
22      first->val=second->val;
23      second->val=tmp;
24  }
Advertisements
This entry was posted in Recursive, Tree. Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s