title: R: creating a recursive binary tree in R
body: <p>I'm interested in writing up a recursive binary tree algorithm. Given the following data where I've already sorted the covariate <code>x</code></p>
  
  <pre><code>mydata &lt;- data.frame(x = c(10, 20, 25, 35), y = c(-10.5, 6.5, 7.5, -7.5))
  &gt; mydata
     x     y
  1 10 -10.5
  2 20   6.5
  3 25   7.5
  4 35  -7.5
  </code></pre>
  
  <p>I will split the tree so that the left node always contains the first instance of the parent node, and the right node contains the rest of the instances in the parent node (weird way of splitting, but please bear with me). Essentially, I want my tree to look like this with a max height = 3.</p>
  
  <pre><code>          [-10.5, 6.5, 7.5, -7.5]
                  /         \
             [-10.5]        [6.5, 7.5, -7.5]
                              /      \
                         [6.5]       [7.5, -7.5]
  </code></pre>
  
  <p>I want the final output of my function to return a list that contains all of the nodes:</p>
  
  <pre><code>&gt; final_tree
  [[1]]
  [[1]][[1]]
     x     y
  1 10 -10.5
  2 20   6.5
  3 25   7.5
  4 35  -7.5
  
  
  [[2]]
  [[2]][[1]]
     x     y
  1 10 -10.5
  
  
  [[2]][[2]]
     x     y
  1 20   6.5
  2 25   7.5
  3 35  -7.5
  
  
  [[3]]
  [[3]][[1]]
  NULL
  
  [[3]][[2]]
  NULL
  
  [[3]][[3]]
     x     y
  1 20   6.5
  
  
  [[3]][[4]]
     x     y
  1 25   7.5
  2 35  -7.5
  </code></pre>
  
  <p>Here's what I have so far:</p>
  
  <pre><code># Initialize empty tree
  create_empty_tree &lt;- function(max_height) sapply(1:max_height, function(k) replicate(2**(k-1),c()))
  
  # Create empty tree with max_height = 3
  tree_struc &lt;- create_empty_tree(max_height = 3)
  
  grow_tree &lt;- function(node_parent, max_height, tree_struc, height){
    # Sort x
    sorted_x &lt;- sort(node_parent$x)
  
    # Fix best split index at 1
    best_split_ind &lt;- 1
  
    # Assign instances to left or right nodes
    group &lt;- ifelse(node_parent$x &lt;= node_parent$x[best_split_ind], "left", "right")
    node_left &lt;- node_parent[which(group == "left"), ]
    node_right &lt;- node_parent[which(group == "right"), ]
  
    # Recursive call on left and right nodes
    if(height &lt; max_height){
    tree_struc[[height]] &lt;- node_parent
    tree_struc[[height + 1]][[1]] &lt;- grow_tree(node_parent = node_left, max_height = max_height, tree_struc = tree_struc, height = height + 1)
    tree_struc[[height + 1]][[2]] &lt;- grow_tree(node_parent = node_right, max_height = max_height, tree_struc = tree_struc, height = height + 1)
    }
  
    return(tree_struc)
  }
  
  grow_tree(node_parent = mydata, max_height = 3, tree_struc = tree_struc, height = 1)
  </code></pre>
  
  <p>The resulting tree is not correct. I think it has to do with how I recursively called the function on the left and right child nodes. Can anyone point me in the right direction?</p>