Understanding insertion of a child

Inserting a child is an operation in which we insert a new node with the given data as the child of a node with the given value in a binary tree. The operation is not as straightforward as inserting at the root and involves two major steps.

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

Step 1: Search for the node with the given value

The first step in inserting a new node as the child of a node with the given value in a binary tree is to find the node, after which the newly created node will be inserted. We can traverse the binary tree to find this node using any traversal operations we have learned.

Algorithm

• Step 1: Check if the `current` node 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 with the given value, the next step is to create a new node and insert it in the tree as the child node of the node we just found. We create a new node with the given data and add it as the left or right child of the node we found, ensuring that we relink the old child of the node. Deciding if the newly created node should be the left or right child is subjective.

Algorithm

• Step 1: Create a new node with the given data.
• Step 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 3: Set the `left` pointer of the node with the given value to hold the reference of the new node.

Algorithm

Combining the above two steps, we can create the algorithm to insert data as the child of a node with the given value in a binary search tree.

Algorithm

• Step 1: If 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 1.4: Return the `current` node.
• Step 2: Go to `Step 1` with the `left` subtree.
• Step 3: Go to `Step 1` with the `right` subtree.
• Step 4: Return the `current` node after both the left and right subtrees are traversed.

Implementation

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 left child.

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 parent node is not found. This would result in traversing a tree with a height of N.

Best Case - Insert a child 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)