title: Why inorder traversal of binary search tree guarantee to have non-decreasing order?
body: <p>TL;DR My ultimate problem is to find the two nodes on a proper binary tree (i.e. itself has at least two nodes) that one is only greater than input, and the other only less than input. (cont. under the line)</p>
  
  <hr>
  
  <p>To implement that, I personally <em>asserted</em> that literally if you draw a tree (decently), you see horizontally the one on the right is by all means greater than any one on its left. </p>
  
  <p>In other words, quoting from Wikipedia (Binary search tree):</p>
  
  <blockquote>
    <p>The key in each node must be greater than all keys stored in the left sub-tree, and smaller than all keys in the right sub-tree.</p>
  </blockquote>
  
  <p>And it seems to only guaranteed to be true locally. With a figure like this:</p>
  
  <pre><code>          A
         /    \
        B      C
      /   \  /   \
     D     E F    G
   /   \
  H     I
  </code></pre>
  
  <p><em>(Letters have no order, i.e. just for structure)</em></p>
  
  <p>By locally I mean when we talk about node E, it's guaranteed that D (with F and G) is smaller than E, but what about C, F, G compared to E, is that also guaranteed?</p>
  
  <p>This seems quite intuitive (that F,C,G are all greater than E), but I don't find anyway to prove that, so is there any counterexample or theoretical proof? Any existed theorems or suggestions?</p>
  
  <hr>
  
  <p><strong>EDIT:</strong> I finally find this equivalent to why is in-order traversal of a binary search tree has a non-decreasing order.</p>