#Feature Request: Adding traversal methods

[souma4]

Recently in Meshes.jl #1168 the idea was suggested to update BinaryTrees with traversal methods. For our uses in that PR, finding the minimum value in the tree and finding the minimum and maximum within a subtree are what's needed. Currently the implementations (_leftmost and _bst_minimum and _bst_maximum) use simple recursion. We should probably find new names too. minimum would make sense to replace _leftmost, just may need a StatsBase import (potentially there's another option, let me know what you think). The subtree minimum-maximum I'm not sure about.

Within that PR there's also find_above_below which traverses the tree to find a key and outputs the adjacent keys. I think this is necessary because you can have

         6
       /    \
      3      other stuff to balance the tree
     /  \
    2    4
   /
  1

and if you want what's below and above two and four, you need to backtrack or store common parents (current implementation).
Would we like to include this since it is functionally an advanced search via traversal?

And as a bonus, we could add the standard full tree traversals, if so desired.
Let me know your perspective, suggestions, etc.

[eliascarv]

Hi @souma4!

_leftmost and _bst_minimum are basically the same function, so they and _bst_maximum can be implemented generically in a new section of the src/binarytree.jl file, like this:

# ----------
# UTILITIES
# ----------

minnode(tree::BinaryTree) = minnode(root(tree))

function minnode(node::BinaryNode)
  leftnode = left(node)
  isnothing(leftnode) ? node : minnode(leftnode)
end

minnode(node::Nothing) = nothing

maxnode(tree::BinaryTree) = maxnode(root(tree))

function maxnode(node::BinaryNode)
  rightnode = right(node)
  isnothing(rightnode) ? node : maxnode(rightnode)
end

maxnode(node::Nothing) = nothing

I think these names are good as they don't conflict with the Base names.

The find_above_below can be implemented in the same section, also using the BinaryTree and BinaryNode APIs.
I would just change the signature and function name to:

function abovebelow(tree::BinaryTree, key)
  # TODO
end

Could you open a PR with these implementations and tests? I can review when I have time.

[souma4]

Quick q, do you also want tests for type stability using these methods in the type stability section? if so, would you like one for each AVLTree type checked right now, or only one? Doing an @inferred for minnode right now on the first AVLTree{Int, Int}() gives

ERROR: return type BinaryTrees.AVLNode{Int64, Int64} does not match inferred return type Union{Nothing, BinaryTrees.AVLNode{Int64, Int64}}

So the return types are a correct subset of the inferred return type. Is this something we should care about or nah? I'm still learning the intricacies of the compiler.

[eliascarv]

Closed by #13