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

To insert a new node as a leaf node, we first need to decide which node in the given tree would be the parent of the newly inserted node. To do this, we have to traverse the tree and identify the first node that does not have either a left child, a right child, or both. This node can act as the parent of our newly inserted node. We can use any traversal algorithms we have learned so far to find this node.

In this example, we will traverse the tree in one direction. This will allow us to reach a leaf node or a node with a free left or right spot.

What traversal algorithm should be used?

The goal is to insert a new node as a leaf in the tree so we can use any tree traversal algorithm. We only need to reach a node that does not have either a left or right child, and then we can insert our new node as its child, making it a leaf node.

Loading Player

1 of 8

Recursive insert a new node with data 9 as the leaf node

Algorithm

Step 1: Look for a free spot from the `root` node.

Step 2: If the `root` node is `null`, create a new node with the given data and return it.

Step 3: Else, if the `root` node does not have a `left` subtree, create and insert the new node as the `left` child of the `root` and return the `root`.

Step 4: Else, if the `root` node does not have a `right` subtree, create and insert the new node as the `right` child of the `root` and return the `root`.

Step 5: Else, recursively call Step 1 with the `left/right` subtree.

Note : We can choose any direction, `left` or `right`, but it should be consistent throughout the traversal

Implementation

C++
Java
Typescript
Javascript
Python

Why only go in one direction when a node has both left and right subtrees?

Let's assume we are at a node X with both left and right subtrees. In that case, we will hit the final else statement and go down in one direction (left in this case). We are guaranteed to find either a leaf node or a node without a left or right node. This is the reason we do not traverse in the other direction when we recurse back to node X.

Complexity Analysis

The insert leaf algorithm traverses the tree until it finds a suitable parent node, so the runtime and space complexity will depend on the traversal algorithm used and how soon we find the parent node. 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, resulting in a tree with a height of N.

However, the runtime complexity depends on the tree's shape and the direction we choose to go if a node has both the left and right subtree. The recursive algorithm will have a linear runtime complexity, such as the trees and directions below.

Loading Image

Worst Case Runtime Complexity

Best Case - The root node can act as a parent node

Space Complexity - O(1)

Time Complexity - O(1)

Worst Case - Unbalanced tree skewed in the direction of traversal

Space Complexity - O(N)

Time Complexity - O(N)