how to create a 2-tree in GPU?

I need to create a tree in GPU and the tree is about 2 M, so there are 2 ways,
1, create in GPU, new tree node in global memory, but how can i dynamically add node in GPU? i tried to do it in kernel, but the function

malloc()

add a new node in local memory which has 16 KB.
2,use array to store the tree, but it’s hard to add a node?

It confused me for a week, i don’t know how to achieve it now.