title: Find all pairs of consecutive numbers in BST
body: <p>I need to write a code that will find all pairs of consecutive numbers in BST.</p>
  
  <p>For example: let's take the BST  T with key 9, T.left.key = 8, T.right.key = 19. There is only one pair - (8, 9).</p>
  
  <p>The naive solution that I thought about is to do any traversal (pre, in, post) on the BST and for each node to find its successor and predecessor, and if one or two of them are consecutive to the node - we'll print them. But the problem is that it'll will the <strong>O(n^2)</strong>, because we have n nodes and for each one of them we use function that takes <strong>O(h)</strong>, that in the worst case h ~ n.</p>
  
  <p>Second solution is to copy all the elements to an array, and to find the consecutive numbers in the array. Here we use <strong>O(n)</strong> additional space, but the runtime is better - <strong>O(n)</strong>.</p>
  
  <p>Can you help me to find an efficient algorithm to do it? I'm trying to think about algorithm that don't use additional space, and its runtime is better than <strong>O(n^2)</strong></p>
  
  <p>*The required output is the number of those pairs (No need to print the pairs).</p>
  
  <p>*any 2 consecutive integers in the BST is a pair.</p>
  
  <p>*The BST containts only integers.</p>
  
  <p>Thank you!</p>