Let's say we have a b tree of order 4 and it has 3 levels. All nodes are completely filled. Now if we want to insert a key with maximum value ( than all keys present in the tree). For this, we have to go to the rightmost node at the last level. As this last level is also filled, now how can we proceed further as all the nodes are full. We cant do a split here. So we are left with creating a new node below the rightmost node. But this tree contradicts the balancing property. I want to know the intuition behind self-balancing nature.

  • 2
    $\begingroup$ When a B-tree node becomes overfull, it is split into two, and a new entry is inserted into the parent. The only way that the height of a B-tree can increase is if the root node splits. $\endgroup$
    – Pseudonym
    Jun 15, 2021 at 4:34

1 Answer 1


That's not how insertion into a full B-tree works. You can read about this in detail in CLRS chapter 18, section 18.2.

In brief, when you want to insert you start at the root and work your way down to the appropriate leaf node, splitting any full nodes you find on the way. That way when you come to insert the new value you are guaranteed that the parent of the node where you do the insert isn't full. There is a special case when the root is full, when you create a new empty root as a parent to the old root, so that the old root can be split. This is the only time that the tree increases in height, and of course it causes every leaf to increase its depth by 1, maintaining the same-depth property.

  • $\begingroup$ yes , now i understood it. Instead of creating a new child node , a new parent node will be created. So the level of each node will get increased by 1. $\endgroup$ Jun 18, 2021 at 2:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.