Is the above a valid binary search tree? It is not -- if our root is 5, the entire left subtree (with 3 as the root) needs to have keys less than the parent tree's root key. Notice that the 8 is still to the left of 5, which is invalidates the simple recursive function from above.

Pattern recognition

In thinking about what we need to do with this tree, there clearly needs to be some form of traversal so that we can check the nodes against each other.

Two questions we can ask are: 1. Is there a way to compare node values without, or possibly exclusive, of the traversal? 2. What technique or pattern can help us easily compare tree values?

The answer is an in-order depth-first search of the tree. As you'll recall, an in-order DFS follows the standard depth-first method of going as deep as possible on each child before going to a sibling node. However, the difference is, it will process all left subtree nodes first, do something with the root or current node, and then process all right subtree nodes.

Because of the definition of a binary search tree, valid ones will produce an in-order DFS traversal in sorted order from least to greatest.

Thus, we can use this to our advantage. Here's a simple inOrder method to run through a binary search tree and return a list of node values.

xxxxxxxxxx

function inOrder(root, output) {

  if (!root) {

    return;

  }

​

  inOrder(root.left, output);

  output.append(root.val);

  inOrder(root.right, output);

}