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. 

Algorithm

• Step 1: Create a new node with the given data.
• Step 2: Set the new node's `left`(or `right`) pointer to hold the reference of the existing `root`.
• Step 3: Return the new node, as this is the new `root`.

2. Insert a parent of a non root node

This is the generic case of inserting a parent. Inserting a node as a parent of a node with the given value in a binary tree involves two major steps.

Algorithm

• Step 1: Search the parent of the node with the given value.
• Step 2: Create and insert the new node.

Step 1: Search the parent of the node with the given value

The first step is to find the node, after which the newly created node will be inserted. This node would be the node's parent, whose value is given. So, instead of searching for the node with the given value, we search for a node whose left or right child has the given value. We can traverse the binary tree to find this node using any traversal operations we have learned so far.

We can piggyback on any of the traversal algorithms we have learned and modify them to look for children's values at every step. This way, we can get the node's address, after which we need to do the insertion.

Algorithm

• Step 1: Check if the `current` node's `left` or `right` child is the node with the given value.
• Step 2: Search the `left` subtree of the `current` node by recursively performing a preorder traversal.
• Step 3: Search the `right` subtree of the `current` node by recursively performing a preorder traversal.

Step 2: Create and insert the new node

Once we find the node after which we have to do the insertion (let's say X), the next step is to create a new node and insert it in the tree as the child node of X. However, we need to make sure that we add it as the correct (left or right) child of X to ensure that the newly inserted node is also the parent of the node whose value we were originally given. If the original node is the left child of its parent, we insert the newly created node as the left child. Otherwise, it is the right child. Also, we need to reconnect any broken links to ensure the tree is not split in two.

Algorithm

• Step 1: If the `left` node of the `current` node is the node with the given value, do the following:
  • Step 1.1: Create a new node with the given data.
  • Step 1.2: Set the `left` pointer of the new node to hold the node's reference stored in the `left` pointer of the node with the given value.
  • Step 1.3: Set the `left` pointer of the node with the given value to hold the reference of the new node.
• Step 2: Else, if the `right` node of the `current` node is the node with the given value, do the following:
  • Step 2.1: Create a new node with the given data.
  • Step 2.2: Set the `right` pointer of the new node to hold the node's reference stored in the `right` pointer of the node with the given value. This will establish the correct reference for the new node.
  • Step 2.3: Set the `right` pointer of the node with the given value to hold the reference of the new node.

Implementation

We need to implement both the cases we examined earlier. The algorithm above can be implemented using any traversal algorithm. In the implementation below, we use preorder traversal to search for the node and insert a new node as its parent.

Complexity Analysis

The above algorithm traverses the binary tree to search for a value, so the runtime complexity depends on the traversal algorithm used. In the worst case, however, the entire tree might have to be traversed, so the runtime complexity is linear. We don't use any extra space apart from the call stack, so the space used is O(h), where h is the tree's height. However, the worst case occurs when the tree is skewed, and the child node is not found. This would result in traversing a tree with a height of N.

Best Case - Insert a parent of the root node

• Space Complexity - O(1)
• Time Complexity - O(1)

Worst Case - Node with the given value is not found, and the tree is skewed

• Space Complexity - O(N)
• Time Complexity - O(N)