Change order of vector of nodes from level order to infix order in r-CodePudding

I have a vector of nodes taken from a binary regression tree. These are in level order, for example, 1,2,4,5,10,11. I would like to place them in infix order like so: 4,2,10,5,11,1. Thanks to Alistaire I have

Suppose we have a vector of your nodes:

nodes <- c(1, 2, 4, 5, 10, 11)

First of all, we only want a binary tree that is of a suitable depth to accommodate your largest node. We can get the required depth by doing:

depth <- ceiling(log(max(nodes), 2))

And a data frame that gives the node number, depth and 'leftness' of a sufficiently large binary tree like this:

df <- data.frame(node = seq(2^(depth) - 1),
                 depth = rep(seq(depth), times = 2^(seq(depth) - 1)),
                 leftness = unlist(sapply(2^seq(depth) - 1, 
                      function(x) (seq(x)[seq(x) %% 2 ==1])/(x   1))))

However, we only need the subset of this tree that matches your nodes:

df <- df[match(nodes, df$node),]

df
#>    node depth leftness
#> 1     1     1   0.5000
#> 2     2     2   0.2500
#> 4     4     3   0.1250
#> 5     5     3   0.3750
#> 10   10     4   0.3125
#> 11   11     4   0.4375

And we can sort the nodes in order according to leftness:

df$node[order(df$leftness)]
#> [1]  4  2 10  5 11  1

Which is your expected result.

To generalize this, just put the above steps in a function:

sort_left <- function(nodes) {
  depth <- ceiling(log(max(nodes), 2))

  df <- data.frame(node = seq(2^(depth) - 1),
                   depth = rep(seq(depth), times = 2^(seq(depth) - 1)),
                   leftness = unlist(sapply(2^seq(depth) - 1, 
                      function(x) (seq(x)[seq(x) %% 2 ==1])/(x   1))))

  df <- df[match(nodes, df$node),]
  df$node[order(df$leftness)]
}

So we can do:

sort_left( c(1, 2, 4, 5, 10, 11))
#> [1]  4  2 10  5 11  1

Or, given the example in your original question,

sort_left(c(1,2,4,5,10,11,20,21))
#> [1]  4  2 20 10 21  5 11  1

Which was the desired result. All without recursion.