Understanding recursive insertion of a leaf

A new node can be easily inserted in the binary tree as a leaf node by recursively going down the tree from top to bottom. The insert process can be summarised in three simple steps, which are given below.

• Step 1: Traverse the tree and find the first node that is missing either a `left` child, a `right` child, or both.
• Step 2: Create a new node with the given data and link it as the missing child of the node found in step 1.

Algorithm