The blog of dlaa.me
Solving puzzles at 30,000 feet [An iterative solution for the "Is this a binary search tree?" programming problem]
Tuesday, April 7th 2015

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.
      • 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.
  • 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. :)
Tags: Miscellaneous Technical
Comments powered by Disqus.