Find Replaced Nodes in BST

Question

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

In a three-tier tree, I approached a 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 four level trees.

  20 15 30 10 17 25 33 9 16 12 18 22 26 31 34 

Being in the root node 15 of the right subtree, 12 is even bigger (violation).

Being in the root node 15 of the left subtree, 16 is even bigger (violation).

So, 16, 12 are the exchange elements in the above BST. How to find them in the program?

Answer 1

One way to think about this problem is to use the fact that the camp tree in order will produce all the elements in sorted order. If you find deviations from the ordered order during this walk, you can try to find two elements that are in the wrong place.

See how to do this for a simple sorted array, then use our algorithm to create something that works on trees. Intuitively, if we start with a sorted array and then replace two (not equal!) Elements, we get a number of elements in the array that will be inappropriate. For example, given an array

 1 2 3 4 5 

If we replace 2 and 4, we get this array:

 1 4 3 2 5 

How would we find that 2 and 4 were replaced here? Well, since 4 is the larger of the two elements and has been resized down, it should be larger than both elements around it. Similarly, since 2 has been replaced, it must be smaller than both elements around it. From this we can conclude that 2 and 4 were replaced.

However, this does not always work correctly. For example, suppose we exchange 1 and 4:

 4 2 3 1 5 

Here, both 2 and 1 are smaller than their neighboring elements, and both 4 and 3 are larger than them. From this it can be said that two of these four somehow changed places, but it is not clear which of them should be changed. However, if we take the largest and smallest of these values ​​(1 and 4, respectively), we get the pairs that have been replaced.

More generally, to find items that have been replaced in sequence, you want to find

• The largest local maximum in the array.
• The smallest local minimum in the array.

These two elements are inappropriate and should be replaced.

Now think about how to apply this to trees. Since moving in order in the tree will result in sorting the sequence with two elements out of order, one option would be to walk in the tree, recording the sequence of order of the elements found, and then using the above algorithm. For example, consider your original BST:

  20 / \ 15 30 / \ / \ 10 17 25 33 / | / \ / \ | \ 9 16 12 18 22 26 31 34 

If we linearize it into an array, we get

 9 10 16 15 12 17 18 20 22 25 26 30 31 33 34 

Notice that 16 is larger than its surrounding elements, and 12 is smaller than it. This immediately tells us that 12 and 16 were replaced.

Thus, a simple algorithm to solve this problem would be to make the tree move in a linear fashion to linearize it into a sequence like a vector or deque , then scan this sequence to find the largest local maximum and the smallest local minimum. This will work in O (n) time using O (n) space. A more complex but more compact algorithm is to track only three nodes at a time - the current node, its predecessor and its successor, which reduces memory usage to O (1).

Hope this helps!

Answer 2

I assume your getMin et getMax works with the hypotheses that the tree is BST, so

 T getMax(tree) { return tree -> right == null ? tree -> value : getMax(tree -> right); } 

(or equivalent code with a loop). If so, your code checks for no more than three values ​​in the tree. Even if getMax and getMin walk the full tree to get the actual maximum / min, you will still base your test on only two comparisons. If you want to verify that your tree satisfies the BST property, it is obvious that you need to examine all the values. It is enough to compare each node with its parent.

 void CheckIsBst(Tree *tree) { if (tree -> left != null) { if (tree -> left -> value > tree -> value) { // print violation } CheckIsBst(tree -> left); } // same with -> right, reversing < to > in the test } 

Edit : this was wrong, see comment. I think this is normal.

 void checkIsBst(Tree *Tree, Tree *lowerBound, Tree *upperBound) { if(lowerBound!= null && lowerBound -> value > tree -> Value) { //violation } // same for upper bound, check with < if (tree -> left != null) { if (tree -> left -> value > tree -> value) { // print violation } CheckIsBst(tree -> left, lowerBound, tree); } // same for right, reversing comparison // setting lowerBound to tree instead of upperBound } 

Call from root with zero bounds

Answer 3

a tree traversal performed by templatetypedef works if you are sure that there is only one exchange. Otherwise, I propose a solution based on your source code:

 int GetMax(TreeNode* tree) { int max_right, max_left, ret; ret = tree->data; if (tree->left != NULL) { max_left = GetMax(tree->left); if (max_left > ret) ret = max_left; } if (tree->right != NULL) { max_right = GetMax(tree->right); if (max_right > ret) ret = max_right; } return ret; } int GetMin(TreeNode* tree) { int min_right, min_left, ret; ret = tree->data; if (tree->left != NULL) { min_left = GetMin(tree->left); if (min_left < ret) ret = min_left; } if (tree->right != NULL) { min_right = GetMin(tree->right); if (min_right < ret) ret = min_right; } return ret; } void print_violations(TreeNode* tree) { if ((tree->left != NULL) && (tree->right != NULL)) { int max_left = GetMax(tree->left); int min_right = GetMin(tree->right); if (max_left > tree->data && min_right < tree->data) { printf("Need to swap %d with %d\n", max_left, min_right); } } if (tree->left != NULL) print_violations(tree->left); if (tree->right != NULL) print_violations(tree->right); } 

It is slower, but it prints all the swaps that it identifies. You can change to print all violations (for example, if (max_left> tree-> data) a printing violation). You can improve performance if you can add two trees to the TreeNode with the maximum and minimum parameters for this subtree.