Algorithm for maintaining balanced binary tree when adding a new node

Question

      _  A _          - depth 1
   _ B       _C_      - depth 2
  D         E   _F_   - depth 3
               G   H  - depth 4

Let's say I have that binary tree and I'd like to add new nodes - I, J, K, L, M, N, O. Values are not no sorted/ordered. The adding node can be any value.

When adding I, it should be added to under B so that depth 3 is well balanced.

      _  A _          - depth 1
   _ B_      _C_      - depth 2
  D    I    E   _F_   - depth 3
               G   H  - depth 4

Now, the J must be under D since depth 3 is full. so is K.

      _  A _          - depth 1
   _ B_      _C_      - depth 2
 _D_   I    E   _F_   - depth 3
J   K          G   H  - depth 4

Of course, L, M, N must be inserted in the same manner.

      _  A  _            - depth 1
   _ B_       _C_        - depth 2
 _D_  _I_   _E_   _F_    - depth 3
J   K L  M  N  O  G  H   - depth 4

In other words, I'm trying to find any missing spots in the tree to add a node before proceeding to the next depth.

I'm looking for an quick algorithm that does this job or reference that explains this algorithm well.

Well... it's an optional thing... but it'd be really awesome if this algorithm can be done with nested set model since I'm applying it to store the whole tree in db. The language I'm using is PHP.

Note:

Sorry, I intentionally skipped this requirement to clarify and focus on the question itself.

The reason why the tree can be imbalanced is that a node without unknown parent will be added to fill an empty spot(like the example) but a node knowing its own parent will be added to under its parent directly (if the parents has already two nodes then it will locate somewhere lower than the parent depth based on the algorithm). For example,

      _  A _          - depth 1
   _ B       _C_      - depth 2
  D         E   _F_   - depth 3
               G   H  - depth 4

Here, let's say node X knows its parent H already. Then, node X will be added to under H. Not a problem.

      _  A _          - depth 1
   _ B       _C_      - depth 2
  D         E   _F_   - depth 3
               G   _H  - depth 4
                  X

Now, node P without a parent is added. Then it should look like this

      _  A _          - depth 1
   _ B_      _C_      - depth 2
  D    P    E   _F_   - depth 3
               G   _H  - depth 4
                  X

And let's say node Z's parent is also F but it's already full. In this case, the algorithm must apply and node Z must be under node G to balance sub-tree of node F.

      _  A _          - depth 1
   _ B_      _C_      - depth 2
  D     P   E   _F_   - depth 3
              _G   _H  - depth 4
             Z    X    - depth 5

A node's knowing its parent is the reason why the whole tree could be imbalanced.

Answer 1

Consider this approach:

At every node, maintain two values:

• Max Left Depth: Maximum depth of a leaf in the left subtree
• Max Right Depth: Maximum depth of a leaf in the right subtree

Choose the direction which has less max depth.

Recurse.

BTW, the example is misleading, you might start from a steady state when two sides are nearly balanced.