The blog of dlaa.me

Sitting on a plane recently looking for a distraction, I recalled a programming challenge by James Michael Hare: Little Puzzlers-Is Tree a Binary Search Tree?. All I had to work with was a web browser, so I used JavaScript to come up with a solution. James subsequently blogged a recursive implementation in C# which is quite elegant. Wikipedia's Binary search tree page uses the same approach and C++ for its verification sample.

Because I did things a little differently, I thought I'd share - along with a few thoughts:

/**
 * Determines if a tree of {value, left, right} nodes is a binary search tree.
 * @param {Object} root Root of the tree to examine.
 * @returns {Boolean} True iff root is a binary search tree.
 */
function isBinarySearchTree(root) {
  var wrapper, node, stack = [{ node: root }];
  while (wrapper = stack.pop()) {
    if (node = wrapper.node) {
      if ((node.value <= wrapper.min) || (wrapper.max <= node.value)) {
        return false;
      }
      stack.push({ node: node.left, min: wrapper.min, max: node.value },
                 { node: node.right, min: node.value, max: wrapper.max });
    }
  }
  return true;
}

Notes:

• Tree nodes are assumed to have a numeric value and references to their left and right nodes (both possibly null).
  • I used the name value (vs. data) because it is slightly more specific.
• I decided on an iterative algorithm because it has two notable advantages over recursion:
  • In the worst case for a tree with N nodes, an iterative solution has bookkeeping for N/2 nodes (when starting to process the leaf nodes of a balanced tree assuming nodes were queued) whereas a recursive solution has bookkeeping for all N nodes (when processing the deepest node of a completely unbalanced tree).
    • Because there are two recursive calls, I don't think tail recursion can be counted on to fix the worst-case behavior.
  • The memory used for bookkeeping by an iterative solution comes from the heap which is generally much larger than the thread stack.
  • To be fair, neither advantage is likely to be significant in practice - but they make good discussion points during an interview. :)
• The iterative algorithm has a disadvantage:
  • Bookkeeping requires an additional object type (wrapper in the code above) which associates the relevant min and max bounds with pending node instances.
    • ... unless you avoid the wrapper by augmenting the node elements themselves.
      • ... which is quite easy in JavaScript thanks to its dynamic type system.
        • ... but still a violation of the separation of concerns principle.
    • The creation/destruction of wrapper objects creates additional memory pressure.
      • Although these objects are short-lived and therefore low-impact for typical garbage collection algorithms.
• I intended the code to be concise, so I made use of assignments in conditional expressions.
  • This is not a practice everyone believes in (myself included!), but it seemed acceptable here.
• The code uses a stack (vs. a queue) because stacks tend to be simpler than queues - especially when implemented with an array.
• I made use of the fact that comparing a number to undefined evaluates to false so I could avoid specifying explicit minimum/maximum values (as in the Wikipedia example) or making HasValue checks (as in James's example).
• If you have a different approach or a suggestion to simplify this one, please share!
  • And note: I'm interested in algorithmic changes, not tweaks like removing extra parenthesis. :)