1<<-DOC
  2Note: Your solution should have O(inorder.length) complexity, since this is what you will be asked to accomplish in an interview.
  3
  4Let's define inorder and preorder traversals of a binary tree as follows:
  5
  6Inorder traversal first visits the left subtree, then the root, then its right subtree;
  7Preorder traversal first visits the root, then its left subtree, then its right subtree.
  8For example, if tree looks like this:
  9
 10    1
 11   / \
 12  2   3
 13 /   / \
 144   5   6
 15then the traversals will be as follows:
 16
 17Inorder traversal: [4, 2, 1, 5, 3, 6]
 18Preorder traversal: [1, 2, 4, 3, 5, 6]
 19Given the inorder and preorder traversals of a binary tree t, but not t itself, restore t and return it.
 20
 21Example
 22
 23For inorder = [4, 2, 1, 5, 3, 6] and preorder = [1, 2, 4, 3, 5, 6], the output should be
 24restoreBinaryTree(inorder, preorder) = {
 25    "value": 1,
 26    "left": {
 27        "value": 2,
 28        "left": {
 29            "value": 4,
 30            "left": null,
 31            "right": null
 32        },
 33        "right": null
 34    },
 35    "right": {
 36        "value": 3,
 37        "left": {
 38            "value": 5,
 39            "left": null,
 40            "right": null
 41        },
 42        "right": {
 43            "value": 6,
 44            "left": null,
 45            "right": null
 46        }
 47    }
 48}
 49For inorder = [2, 5] and preorder = [5, 2], the output should be
 50restoreBinaryTree(inorder, preorder) = {
 51    "value": 5,
 52    "left": {
 53        "value": 2,
 54        "left": null,
 55        "right": null
 56    },
 57    "right": null
 58}
 59Input/Output
 60
 61[time limit] 4000ms (rb)
 62[input] array.integer inorder
 63
 64An inorder traversal of the tree. It is guaranteed that all numbers in the tree are pairwise distinct.
 65
 66Guaranteed constraints:
 671 ≤ inorder.length ≤ 2 · 103,
 68-105 ≤ inorder[i] ≤ 105.
 69
 70[input] array.integer preorder
 71
 72A preorder traversal of the tree.
 73
 74Guaranteed constraints:
 75preorder.length = inorder.length,
 76-105 ≤ preorder[i] ≤ 105.
 77
 78[output] tree.integer
 79
 80The restored binary tree.
 81http://www.geeksforgeeks.org/construct-tree-from-given-inorder-and-preorder-traversal/
 82DOC
 83
 84describe "#restore_binary_tree" do
 85  def restore_binary_tree(inorder, preorder)
 86    return nil if inorder.empty?
 87
 88    value = preorder.shift
 89    pivot = inorder.index(value)
 90    {
 91      value: value,
 92      left: pivot.zero? ? nil : restore_binary_tree(inorder[0..(pivot-1)], preorder[0..pivot]),
 93      right: restore_binary_tree(inorder[pivot+1..-1], preorder[pivot..-1])
 94    }
 95  end
 96
 97  null = nil
 98  [
 99    { inorder: [4, 2, 1, 5, 3, 6], preorder: [1, 2, 4, 3, 5, 6], x: { "value": 1, "left": { "value": 2, "left": { "value": 4, "left": null, "right": null }, "right": null }, "right": { "value": 3, "left": { "value": 5, "left": null, "right": null }, "right": { "value": 6, "left": null, "right": null } } } },
100    { inorder: [2, 5], preorder: [5, 2], x: { "value": 5, "left": { "value": 2, "left": null, "right": null }, "right": null } },
101    { inorder: [100], preorder: [100], x: { "value": 100, "left": null, "right": null } },
102    { inorder: [-100000, -99999, -99998], preorder: [-99999, -100000, -99998], x: { "value": -99999, "left": { "value": -100000, "left": null, "right": null }, "right": { "value": -99998, "left": null, "right": null } } },
103  ].each do |x|
104    it do
105      $preorder_index = 0
106      expect(restore_binary_tree(x[:inorder], x[:preorder])).to eql(x[:x])
107    end
108  end
109end