How to create a binary tree using only base R?

user_13930389 0
Viewed 949

What is the optimal way (assuming that, in this case, optimal means "the fastest way to create or access") of creating a binary tree using only base R capabilities/tools? I'm assuming some form of recursion and/or data structures using environment manipulation would be necessary?

More so, I'd like the binary tree creation to be parameterized as in what type of tree should be generated (for example: a perfect one, where all nodes have two children, or not?).

Example:

my_tree <- grow_tree(perfect = FALSE, max_height = 3)
print(my_tree)

my_tree[1]
1

my_tree[1][left]
2

my_tree[1][right]
3

my_tree[1][left][left]
4

Should be a representation of a tree that looks like:

    1
   / \
  2   3
 /
4

Note: feel free to use S3 or S4, considering they are provided in base R. However, it would be interesting to see a solution without them.

binary-tree r
1 Answers

Below we use only base for the graph calculations. We only use the igraph package for plotting and any calculation needed only for plotting.

A simple approach is to store a binary tree as an array by storing the 2 children of the node at position i in positions 2*i+0:1. For the tree in the example see the code below. This allows simple breadth first traversal (just run through the array skipping over NAs), and finding the position of parent (floor(i/2)) and children (formula in first sentence) where i is the position of a node.

a <- numeric()
a[1] <- 1
a[2:3] <- 2:3 # 2*1+0:1 = 2:3
a[4] <- 4  # 2*2+0 = 4

Graphics

In this approach we mark each node as - if it is a left child and + if it is a right child. If there are two children to a particular parent this will plot them to the left and right of the parent. If there is one child then it will be plotted directly under the parent but you can tell whether it is a left or right child by the sign. In a later section we show how to plot all children to the left or right of their parent even if that parent has only one child; however, this approach here involves less code.

library(igraph)

ix <- seq_along(a)
edges <- cbind(ix, floor(ix/2))[-1, ]
# label right child as + and left child as - .  Root is +1.
edges <- apply(edges, 2, function(x) paste0(ifelse(x %% 2, "+", "-"), x))
g <- graph_from_edgelist(edges)
plot(g, layout = layout_as_tree(g, root = "+1", mode = "all"))

(continued after image) screenshot

Generate random graph

Here is an example of generating a random tree of depth no more than n. (The igraph author helped simplify the initial plotting code I had posted).

library(igraph)

set.seed(7)
n <- 4
a <- rnorm(2^n-1)
 
a[-1] <- ifelse(runif(length(a)) > .8, NA, a)[-1]  # -1 to exclude root
for(i in seq_along(a)) if (i > 1 && is.na(a[floor(i/2)])) a[i] <- NA
a
##  [1]  2.2872471613405239 -1.1967716822223495 -0.6942925104354590
##  [4] -0.4122929511368025 -0.9706733411194832                  NA
##  [7]  0.7481393402905512 -0.1169552258871516                  NA
## [10]  2.1899781073293796  0.3569862303290225                  NA
## [13]                  NA  0.3240205401385159                  NA

Now plot it.

library(igraph)

# create graph from edgelist
make_graph <- function(edgelist) {
  edges <- apply(edgelist, 2, as.character)
  graph_from_edgelist(edges)
}

# create full graph layout without random NAs
ix <- seq_along(a)
edges_f <- cbind(ix[-1], floor(ix[-1]/2))
g_f <- make_graph(edges_f)
layout_f <- layout_as_tree(g_f, root = "1", mode = "all")

# create random subset graph by removing edges connected to NA nodes
edges_s <- na.omit(edges_f + 0*replace(edges_f, TRUE, a[c(edges_f)]))
g_s <- make_graph(edges_s)

# plot using corresponding layout rows from full graph
plot(g_s, layout = layout_f[names(V(g_f)) %in% names(V(g_s)), ])

screenshot

Update

Have updated last section so that graph always shows left child to left of parent and right child to right of parent. It previously did this if there were two children but now it also does that if there is only one child.

user_5165480
Related