Understanding insertion of a parent

Inserting a parent is an operation where we have to insert a new node with the given data as the parent of a node with the given value in a binary tree. Inserting a node as a parent is more complex than inserting it as a child. This is because, unlike when inserting the node as a child, in this case, we have first to search for the parent of the node with the given value to get the insertion position. This is not straightforward, and we will have to consider two cases.

1. Insert a parent of the root node

In this case, since we have to insert a node as the parent of the root node, we are essentially changing the tree's root node. Also, since the root node has no parent, we cannot use our generic algorithm to search for the parent of a node with the given value, so we will have to deal with this edge case separately.