# Find all wrong pairs in a BST

## Problem

A binary tree is given. Which is supposed to be a BST, but it has some errors. Find all the pair of numbers which are not following the BST rule

## Solution

In a BST all numbers in the left subtree of a node should be less than the node and all numbers in the right subtree of the node should be greater than the node. So given a node we can say what is the valid range of numbers in the left subtree and what is for the right. As long as the numbers in the node is in that range, it is fine. When some node breaks this range, then we print the pair of wrong numbers and create two ranges for its children. one range is to find the wrong pair considering its ancestors and another range is for a tree considering that wrong node as a root of a new BST.

## Code

package dsalgo; public class BinaryTreeWrongPairs { public static void main(String[] args) { Node a = new Node(5); Node b = new Node(10); Node c = new Node(14); Node d = new Node(6); Node e = new Node(3); a.left = b; a.right = c; b.left = d; c.right = e; findWrongPairsIn(a, null); } public static void findWrongPairsIn(Node root, Range range) { if (range == null) { range = new Range(Integer.MIN_VALUE, Integer.MAX_VALUE); } if (root == null) { return; } if (root.isNotIn(range)) { root.printTheWrongPairForThis(range); findWrongPairsIn(root.left, range); findWrongPairsIn(root.right, range); } findWrongPairsIn(root.left, root.newLeft(range)); findWrongPairsIn(root.right, root.newRight(range)); } } class Node { Node left; Node right; int value; public Node(int value) { this.value = value; } public boolean isNotIn(Range range) { if (value >= range.min && value <= range.max) { return false; } return true; } public Range newLeft(Range range) { int min = isNotIn(range) ? Integer.MIN_VALUE : range.min; return new Range(min, value); } public Range newRight(Range range) { int max = isNotIn(range) ? Integer.MAX_VALUE : range.max; return new Range(value, max); } public void printTheWrongPairForThis(Range range) { if (range.min > value) { System.out.println(range.min + "," + value); } if (range.max < value) { System.out.println(range.max + "," + value); } } } class Range { int min; int max; public Range(int min, int max) { this.min = min; this.max = max; } }