# Tree random element

**URL:** <https://forum.elixirforum.com/t/tree-random-element/34553>\
**Category:** Coding Challenges\
**Tags:** coding-challenge, trees, random\
**Created:** [September 24, 2020, 11:44am UTC](https://forum.elixirforum.com/t/tree-random-element/34553 "2020-09-24T11:44:11Z")\
**Posts on this page:** 4\
**Page:** 1

<div class="post-metadata">

**Author:** ![BorjaEst](https://forum.elixirforum.com/user_avatar/forum.elixirforum.com/borjaest/32/19583_2.png) [@BorjaEst](https://forum.elixirforum.com/u/BorjaEst)\
**Post date:** [September 24, 2020, 11:44am UTC](https://forum.elixirforum.com/t/tree-random-element/34553/1 "2020-09-24T11:44:12Z")

</div>

Trees (specially gb\_trees) are a very efficient/fast tool to store Key-Value. However, depending on the program it’s usage cat get a bit more complicated.

Here goes my challenge.  
What would be the most efficient way to get a random element and it’s path from a gb\_tree?

---

<div class="post-metadata">

**Author:** ![al2o3cr](https://forum.elixirforum.com/user_avatar/forum.elixirforum.com/al2o3cr/32/3457_2.png) [@al2o3cr](https://forum.elixirforum.com/u/al2o3cr)\
**Post date:** [September 24, 2020, 12:07pm UTC](https://forum.elixirforum.com/t/tree-random-element/34553/2 "2020-09-24T12:07:41Z")

</div>

`:gb_trees.iterator/1` plus a reservoir sampling algorithm?

---

<div class="post-metadata">

**Author:** ![BorjaEst](https://forum.elixirforum.com/user_avatar/forum.elixirforum.com/borjaest/32/19583_2.png) [@BorjaEst](https://forum.elixirforum.com/u/BorjaEst)\
**Post date:** [September 24, 2020, 12:49pm UTC](https://forum.elixirforum.com/t/tree-random-element/34553/3 "2020-09-24T12:49:23Z")

</div>

The idea is good if we don’t want to cover the whole tree (just the k first), however to cover the whole tree, wouldn’t we have to execute rand:random() in each iteration (rand operations are quite expensive)?

---

<div class="post-metadata">

**Author:** ![BorjaEst](https://forum.elixirforum.com/user_avatar/forum.elixirforum.com/borjaest/32/19583_2.png) [@BorjaEst](https://forum.elixirforum.com/u/BorjaEst)\
**Post date:** [September 26, 2020, 2:49pm UTC](https://forum.elixirforum.com/t/tree-random-element/34553/4 "2020-09-26T14:49:03Z")

</div>

So after thinking about it, my solution would be something like this:

```elixir
iex(1)> tree = :gb_tree.example() #Any f that returns a tree
{3, {:a, 1, nil, {:b, 2, nil, {:c, 3, nil, nil}}}}
iex(2)> n = :rand.uniform(:gb_trees.size(tree))
2
iex(11)> iter = :gb_trees.iterator(tree) 
[{:a, 1, nil, {:b, 2, nil, {:c, 3, nil, nil}}}]
iex(14)> {k,v,_}=Enum.reduce(1..n, {:nil,:nil,:gb_trees.iterator(tree)}, fn _, {_,_,i} -> :gb_trees.next(i) end)
{:b, 2, [{:c, 3, nil, nil}]}

```

However I am thinking, now gb\_trees are not used any longer as we do have maps.