This breaks normalization, but it's similar to something I have done in production... and it may work for you.
In addition to your table of tree nodes:
CREATE TABLE TreeNode
NodeID PRIMARY KEY
Data -- or whatever
Create a table of top-to-bottom paths:
CREATE TABLE TreePath
TopNodeID, -- assuming the roots are at the top
BottomNodeID, -- assuming the leaves are at the bottom
Path, -- more on this later
Length int -- number of edges in the path
Primary key: (TopNodeID, BottomNodeID)
Whenever you insert a node into the tree, add the new paths into TreePath.