Flipkart Interview Question
Software Engineer / DevelopersCountry: India
Interview Type: Phone Interview
@csemanoj: That wouldn't be the condition that would make this solution right. Adjacent nodes in a BST are not always in-order successors, and not all in-order successors are adjacent. To make inversion counting correct, you'd have to have a condition that says you can only swap in-order successors, but that seems very contrived.
Inorder traversal and Inversion count is the right
answer !!
But assuming to swap only adjacent nodes may not be a good.
Simply improvise the inversion count algorithm to do a divide and conquer approach with a midpoint for the inorder array and figure out all the swaps required not just adjacent.
Perform Inorder traversal of binary tree and then Inversion Count on the formed array.
- csemanoj May 19, 2014The inversion count will be the minimum number of swaps required to bring the array in ascending order which is inorder of BST.