Adding an element to the first non-occupied leaf in a binary tree

Question

Right now I'm trying to write a binary heap in Java implemented over a binary tree structure, and while I do have a very good grasp on how to "heapify" the tree after adding an element, the logic for finding the first unoccupied leaf at the bottom of the heap eludes me.

I'm aware that finding the first unoccupied leaf is supposed to be a breadth-first traversal, but I still can't figure out how exactly a breadth-first traversal algorithm would work.

Answer 1

This is what a breadth-first search for the first null branch (followed by an insertion to the branch) would look like. Note that this is basically the same as a depth-first insert, except that this uses a queue where a depth-first insert uses a stack.

void breadthFirstInsert(Node root, Object obj) {
    Queue<Node> queue = new LinkedList<>();
    queue.offer(root);
    while(!queue.isEmpty()) {
        Node temp = queue.poll();
        if(temp.left != null) {
            queue.offer(temp.left);
        } else {
            temp.left = new Node(obj);
            return;
        }
        if(temp.right != null) {
            queue.offer(temp.right);
        } else {
            temp.right = new Node(obj);
            return;
        }
    }
}