# Binary Tree vs Linear Lookup

## JavaScript performance comparison

Test case created by Josh Perry

## Info

Compares the speed of looking up of a value from a flat list and from a binary tree.

## Preparation code

``<script src="https://ajax.googleapis.com/ajax/libs/jquery/1/jquery.min.js"></script><script>  Benchmark.prototype.setup = function() {    function leftNode(nodeidx) {      return (2 * nodeidx) + 1;    }        function rightNode(nodeidx) {      return (2 * nodeidx) + 2;    }        function addValueToNode(tree, nodeidx, value) {      var currentidx = nodeidx;      while (true) {        if (value > tree[currentidx]) {          var right = rightNode(currentidx);          if (!tree[right]) {            tree[right] = value;            break;          } else currentidx = right;        } else {          var left = leftNode(currentidx);          if (!tree[left]) {            tree[left] = value;            break;          } else currentidx = left;        }      }    }        function addValueToTree(tree, value) {      if (tree.length == 0) tree.push(value)      else addValueToNode(tree, 0, value);    }        function addValuesToTree(tree, values) {      for (var i = 0; i < values.length; i++)      addValueToTree(tree, values[i]);    }        function addDictionaryToTree(tree, dict) {      var values = [];      for (var key in dict) {        values.push(key);      }      values.sort();      addValuesToTree(tree, values);    }        function inOrder(tree, nodeidx, func) {      if (tree[nodeidx]) {        //traverse the left subtree        var leftidx = leftNode(nodeidx);        var leftval = tree[leftidx];        if (leftval !== null) {          inOrder(tree, leftidx, func);        }            if (!func(tree[nodeidx])) return;            var rightidx = leftNode(nodeidx);        var rightval = tree[rightidx];        //traverse the right subtree        if (rightval !== null) {          inOrder(tree, rightidx, func);        }      }    }        var tree = [];    var values = [];    for (var i = 0; i < 10000; i++) {      var val = Math.random() * 1000      while (values.indexOf(val) >= 0)      val = Math.random() * 1000          values.push(val);    }    addValuesToTree(tree, values);        var lookupValues = [];    for (var i = 0; i < 1000; i++) {      var val = Math.random() * 1000      while (lookupValues.indexOf(val) >= 0)      val = Math.random() * 1000          lookupValues.push(val);    }    var lookupLength = lookupValues.length;            function findClosestValue(tree, nodeidx, needle) {      var found = 0;          inOrder(tree, nodeidx, function(nodeval) {        if (nodeval < needle) {          found = nodeval;          return true;        }            return false;      });          return found;    }        function naiveFindClosestValue(haystack, needle) {      var result;          for (var key in haystack) {        var dist = key - needle;            if ((dist < 0 && dist < result) || result === undefined) {          result = key;        }      }          return result;    }        function rand(from, to) {      return Math.floor(Math.random() * (to - from + 1) + from);    }  };</script>``

## Test runner

Warning! For accurate results, please disable Firebug before running the tests. (Why?)

Java applet disabled.

Testing in unknown unknown
Test Ops/sec
Linear Lookup
``naiveFindClosestValue(values, lookupValues[rand(0, lookupLength - 1)]);``
pending…
B-Tree Lookup
``findClosestValue(tree, 0, lookupValues[rand(0, lookupLength - 1)]);``
pending…

You can edit these tests or add even more tests to this page by appending `/edit` to the URL.