CareerCup

One way is to do in order traversal of the tree and look for count inversions, means whether the next number is smaller than the other. O(nlogn)

We will do this by doing a pre order traversal by the tree and maintaining of stack of conditions at each node. i.e. if we are traversing the left tree then we add a condition (< value of node) and if right then condition (>= value of node). These are the conditions that a BST satisfies. For each node check which conditions is doesn't satisfy in the stack and print the pair for which it doesn't satisfy the condition. Running time n nodes and logn comparisons for each node no n*log(n)

You can solve in O(n*logn*logn), which is even better than O(n^2):

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Collections;

namespace PrintWrongPairsInBST
{
    class Program
    {
        static void Main(string[] args)
        {
            //Tree:
            //                   7
            //      2                            19
            //   8     5                   12        17
            //       13                            21
            //                                   46
            //Which isnt sorted

            Tree t = new Tree(7);
            t.left = new Tree(2);
            t.right = new Tree(19);
            t.left.left = new Tree(8);
            t.left.right = new Tree(5);
            t.right.left = new Tree(12);
            t.right.right = new Tree(17);
            t.left.right.left = new Tree(13);
            t.right.right.left = new Tree(21);
            t.right.right.left.left = new Tree(46);

            Process(t,
                    new LinkedList<int>(),
                    new LinkedList<char>());
        }

        static void Process(Tree t,
                            LinkedList<int> value,
                            LinkedList<char> direction)
        {
            if (t == null) //Very base case
            {
                return;
            }

            if (t.left == null && t.right == null) //Leaf
            {
                if (value.Count > 0)
                {
                    int[] pathValue = new int[value.Count + 1];
                    int index = 0;
                    foreach (int v in value)
                    {
                        pathValue[index++] = v;
                    }
                    pathValue[index++] = t.info;

                    char[] pathDirection = new char[direction.Count + 1];
                    index = 0;
                    foreach (char d in direction)
                    {
                        pathDirection[index++] = d;
                    }
                    pathDirection[index++] = 'U';

                    ProcessPath(pathValue,
                                pathDirection);
                }
                return;
            }

            //Induction
            value.AddLast(t.info);
            direction.AddLast('L');
            Process(t.left,
                    value,
                    direction);
            value.RemoveLast();
            direction.RemoveLast();

            value.AddLast(t.info);
            direction.AddLast('R');
            Process(t.right,
                    value,
                    direction);
            value.RemoveLast();
            direction.RemoveLast();
        }

        static void ProcessPath(int[] value,
                                char[] direction)
        {
            for (int i = value.Length - 1; i >= 0; i--)
            {
                for (int j = i - 1; j >= 0; j--)
                {
                    if (direction[j] == 'L')
                    {
                        if (value[i] > value[j])
                        {
                            Console.WriteLine("({0}, {1})", value[i], value[j]);
                        }
                    }
                    else if (direction[j] == 'R')
                    {
                        if (value[i] < value[j])
                        {
                            Console.WriteLine("({0}, {1})", value[i], value[j]);
                        }
                    }
                }
            }
        }
    }

    class Tree
    {
        public int info = 0;
        public Tree left = null;
        public Tree right = null;

        public Tree(int info)
        {
            this.info = info;
            this.left = null;
            this.right = null;
        }
    }
}

Solution:
(8, 2)
(8, 7)
(13, 5)
(13, 7)
(46, 21)
(46, 17)
(21, 17)
(17, 19)