https://www.geeksforgeeks.org/fix-two-swapped-nodes-of-bst/
Two of the nodes of a Binary Search Tree (BST) are swapped. Fix (or correct) the BST.
1. The swapped nodes are not adjacent in the inorder traversal of the BST.
2. The swapped nodes are adjacent in the inorder traversal of BST.
http://k2code.blogspot.com/2015/09/given-bst-with-2-nodes-swapped-fix-it.html
A simple method is to store inorder traversal of the input tree in an auxiliary array. Sort the auxiliary array. Finally, insert the auxiilary array elements back to the BST, keeping the structure of the BST same. Time complexity of this method is O(nLogn) and auxiliary space needed is O(n).
1. Initialize firstStartPoint = null, lastEndPoint = null, previous_node = null
http://k2code.blogspot.com/2015/09/given-binary-search-tree-with-2-nodes.html
Given a binary search tree with 2 nodes swapped, give the number of nodes not following bst property.
Now we swap 8 and 20, and BST is changed.
Now number of pairs not following BST property are 3. The reason is :
We can have following solution:
http://k2code.blogspot.in/2013/08/inversions.html
Read full article from Two nodes of a BST are swapped, correct the BST | GeeksforGeeks
Two of the nodes of a Binary Search Tree (BST) are swapped. Fix (or correct) the BST.
1. The swapped nodes are not adjacent in the inorder traversal of the BST.
The inorder traversal of the given tree is 3 25 7 8 10 15 20 5
If we observe carefully, during inorder traversal, we find node 7 is smaller than the previous visited node 25. Here save the context of node 25 (previous node). Again, we find that node 5 is smaller than the previous node 20. This time, we save the context of node 5 ( current node ). Finally swap the two node’s values.2. The swapped nodes are adjacent in the inorder traversal of BST.
The inorder traversal of the given tree is 3 5 8 7 10 15 20 25
Unlike case #1, here only one point exists where a node value is smaller than previous node value. e.g. node 7 is smaller than node 8.
We will maintain three pointers, first, middle and last. When we find the first point where current node value is smaller than previous node value, we update the first with the previous node & middle with the current node. When we find the second point where current node value is smaller than previous node value, we update the last with the current node. In case #2, we will never find the second point. So, last pointer will not be updated. After processing, if the last node value is null, then two swapped nodes of BST are adjacent.
private void swap(Node a, Node b) { if (n1 == null || n2 == null) return; int tmp = a.val; a.val = b.val; b.val = tmp; } public void recoverTree(Node root) { Node cur = root, pre = null, first = null, second = null; // in order travesal should return a sorted list Stack<node> stack = new Stack<node>(); while (cur != null) { // find the left most child stack.push(cur); cur = cur.left; } while (!stack.isEmpty()) { cur = stack.pop(); // is it wrong? if (pre != null && cur.val < pre.val) { if (first == null) { // the first wrong item should be the bigger one first = pre; second = cur; // there is a chance that the two were swapped } else { // the second wrong item should be the smaller one second = cur; break; } } // go to right child and repeat pre = cur; cur = cur.right; while (cur != null) { stack.push(cur); cur = cur.left; } } swap(first, second); } A simple method is to store inorder traversal of the input tree in an auxiliary array. Sort the auxiliary array. Finally, insert the auxiilary array elements back to the BST, keeping the structure of the BST same. Time complexity of this method is O(nLogn) and auxiliary space needed is O(n).
http://www.ideserve.co.in/learn/how-to-recover-a-binary-search-tree-if-two-nodes-are-swapped
1. Initialize firstStartPoint = null, lastEndPoint = null, previous_node = null
2. Visit all nodes of a tree in in-order fashion. Keep track of previously visited node.
3. At each node that is being visited,
if value of previously visited node > current node
{
if(firstStartPoint == null)
{
firstStartPoint = previous_node
}
lastEndPoint = current_node;
}
4. After all nodes are visited :swap firstStartPoint with lastEndPoint
TreeNode firstStartPoint, lastEndPoint; TreeNode prevNode; public void findSegments(TreeNode root) { if (root == null) return; findSegments (root.left); if (prevNode != null) { if (prevNode.val > root.val) { if (firstStartPoint == null) { firstStartPoint = prevNode; } lastEndPoint = root; } } prevNode = root; findSegments (root.right); } public void recoverTree(TreeNode root) { findSegments(root); int x = firstStartPoint.val; firstStartPoint.val = lastEndPoint.val; lastEndPoint.val = x; }Given a binary search tree with 2 nodes swapped, give the number of nodes not following bst property.
Now we swap 8 and 20, and BST is changed.
1
2
3
4
5
6
7
8
| Input Tree: 10 / \ 5 8 / \ 2 20In the above tree, nodes 20 and 8 must be swapped to fix the tree. |
- 10-20
- 10-8
- 20-8
We can have following solution:
- Find the inorder traversal of the input tree. Example - 2, 5, 20, 10, 8
- Find the number of inversions in the inorder traversal. That is the answer. Here the inversions are 20-10, 20-8, and 10-8.
http://k2code.blogspot.in/2013/08/inversions.html
int countInversions(int[] a) { return countInversions(a, 0, a.length, new int[a.length]);}int countInversions(int[] a, int start, int end, int[] t) { if (start == end - 1) return 0; int mid = (start + end) / 2; int x = countInversions(a, start, mid, t); int y = countInversions(a, mid, end, t); int z = subroutine(a, start, mid, end, t); return x + y + z;}int subroutine(int[] a, int start, int mid, int end, int[] t) { int i = start; int j = mid; int k = i; int count = 0; while (i < mid && j < end) if (a[i] < a[j]) t[k++] = a[i++]; else { t[k++] = a[j++]; count += (mid - i); } System.arraycopy(a, i, t, k, mid - i); System.arraycopy(a, j, t, k, end - j); System.arraycopy(t, start, a, start, end - start); return count;}