Chapter 21, Problem 12RQE

Explanation of Solution

Pseudocode algorithm to insert a node in a binary tree:

Inserting a node:

While inserting a new node in the binary tree, it searches for the leaf position to insert a node. So, it starts to search the key from root until it finds the leaf node.

• Once the leaf node is found, it adds the new node as a child of the leaf node. Otherwise, it returns the new node.

Psuedocode:

In this algorithm, let us consider the root node as “root” and key as “k” and the “left” represents the left subtree whereas the “right” represents the right subtree.

Input: Binary tree

Output: Display the binary tree after inserting a new node.

Process: Insert(Node root, Key k)

Algorithm:

if (root == null)

return new Node(k);

elseif (k <= root...