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 does not have a `left` or `right` subtree.
• Step 2: Create a new node with the given data and link it to the node found in step 1.

Algorithm