do we need to recompute the tree every time the ray direction's changes?

No you compute the tree based on the world and traverse it based on the ray. No need to recompute tree every ray trace

this reminds me of clip_triangle

How does K-D trees handle triangles that overlap the split? Is it based on the center?

Does it matter if the tree is not balanced? or if we did any work/special treatment in the algorithm to keep it balanced?

I believe an unbalanced kd-tree would lead to poor performance