Make it explicit that it is a binary tree
Your class name is Tree, but there are many different types of trees. Make it clear that this is a binary tree, and name it BinaryTree.
Move class Node inside class Tree
Move the declaration of class Node inside that of class Tree, in the public section. This makes it clear that this Node is specific to the tree ...
A few extra points to the current answers:
Tree will create a default copy constructor which will not behave as expected.
As root is a raw pointer it will just do a shallow copy, assuming T is copiable (i.e. create a new pointer to the same data.)
This will create unexpected behaviour if you copy the Tree and then modify one of the copies.
As they both ...
There's no way to access the tree's nodes, so contain_sub is useless to clients.
Even if it works, contain_sub doesn't return anything in two of its branches and looks gnarly.
Use smart pointers or have a good reason not to.
Don't copy items unless you're copying the tree itself; you're doing this a lot.
Regarding iterators: remember that there are multiple ...
tooShortNoChildren is subsumed in notDeepEnoughYet. The newtypes and class are silly, discard them. treeWalker doesn't touch cache, so let's hide cache in a monadic interface.
-- walks through all nodes of specified depth and applies a function
treeWalker :: ([Int] -> LinkedTree -> State [a] LinkedTree) -- function to apply on every node of desired ...
In general in F# we try to minimize the use of explicit type declaration on function arguments:
let left (node: Node<'a>) = node.Left
let left node = node.Left
The function insertNode violates the single responsibility principle in that if root = None then it creates a new tree/root node instead of actual inserting the value.