Inserting a node to highest level node if it is available in Haskell

I created a tree and its data type is that:

data Tree = Empty | Node Int Int Tree Tree Tree

My first Int is actual data. Second Int is the number of children, meaning this node can store how many children. Even if it is ternary tree, if the number of children is two, then it should store two children.

My problem is that after I created a function inserter tree node, it will take nodes from list and it will insert to the highest level node which is available (this means if number of children is not full still). This is a example:

                              a
                             / \
                            b   c
                           / 
                          d
                         /
                        e

For example, 'd' can store only two children(its second Int value is two), but it has one child. Also, 'b' can store only two children, but it has one child. Now, my list has two node, and I will insert these nodes. Firstly, I need to fill 'd', then I will fill 'b' node, so they will reach their number of children. (Let's say my list [k,l]). The end of my process will be that:

                              a
                             / \
                            b   c
                           / \
                          d   l
                         / \
                        e   k

I thought to implement the classic recursive method:

inserter (Node _ num first second third) node
 | num/=0     = Node _ num (inserter first node) (inserter second node) (inserter third node)
 | otherwise  = insert (Node _ num first second third) node

(insert is other function I wrote, and I did taking from list part to use this function)

When I do that it will insert first available node, I need to pass until found highest level node which is available. Could you give an idea , or a way I can follow?

Break the problem down into smaller parts. If inserter is inserting a list of nodes, first try writing a function (let's call it inserter1) that inserts just 1 node at the highest available level. Then you can write inserter in terms of that function.

Start with the type signature. I'm assuming here that when you say "insert a node" you mean "insert a tree". Then inserter1 has type Tree -> Tree -> Tree.

To define inserter1, first think about the simplest base cases and work from there. The simplest case is inserting into an empty tree:

inserter1 :: Tree -> Tree -> Tree
inserter1 Empty node = node

The next simplest case would be inserting into a tree with one level:

inserter1 (Node i n Empty Empty Empty) node
  | n > 0     = Node i n node Empty Empty -- There is room
  | otherwise = _ -- What to do when there is no room? 

Here we run into the question of what to return if there isn't room to insert something. If n is 0, we can't successfully insert node! This suggests we should have a concept of "failing to insert" in the return type. A common pattern for this is to use Maybe, which means change the type of inserter1 to Tree -> Tree -> Maybe Tree. Now we can return Nothing in the second case:

inserter1 :: Tree -> Tree -> Maybe Tree
inserter1 Empty node = Just node
inserter1 (Node i n Empty Empty Empty) node
  | n > 0     = Just (Node i n node Empty Empty)
  | otherwise = Nothing

The recursive case is when you have multiple choices at the current level of where to insert, i.e. there are available Emptys on this level AND child nodes that might be preferable. In this case, we want to try inserting into the child nodes first, and only resort to inserting on this level if inserting into the child nodes fail because they are full. Here is what it looks like for one child node:

inserter1 (Node i n t1 Empty Empty) node =
  -- Should we insert into child `t1` or replace an `Empty` on this level? Inserting into child nodes is preferable, so try it first.
  case inserter1 t1 node of
    -- The insertion to `t1` worked and became `t1'`, so replace it and we're done!
    Just t1' -> Just (Node i n t1' Empty Empty)
    -- `t1` must have been full, so see if there is room to insert on this level
    Nothing
      -- There is room
      | n > 1 -> Just (Node i n t1 node Empty)
      | otherwise -> Nothing

Hopefully this gives some direction to help you complete the definition. I would suggest adding a case for two non-empty children, then for three non-empty children. Try to get it working first, even if it feels like you are writing too many cases. Once you have something working, it is often easier to see how it can be simplified.