Understanding iterative insertion of a leaf

As we learned earlier, the recursive traversal algorithm performs poorly for some binary tree structures because of the choice of moving only in one direction. There is another way to insert a leaf node that will perform better in those cases. We can use the iterative level order traversal to insert a leaf node.

Algorithm

The algorithm is still the same. We move in the tree using the level order traversal algorithm. This way, we only move to the next level once we have checked all the nodes for the current level.

Iterative insert a new node with value 9 as the leaf node

Algorithm

  • Step 1: Add the `root` node to the traversal queue.
  • Step 2: While the queue is not empty, do the following:
    • Step 2.1: Pop the first node from the queue.
    • Step 2.2: If the `left` child of the popped node is `null`, insert the new node as its left child and return the `root` node.
    • Step 2.3: Else, if the `left` child of the popped node is not `null`, add it to the queue.
    • Step 2.4: If the `right` child of the popped node is `null`, insert the new node as its right child and return the `root` node.
    • Step 2.5: Else, if the `right` child of the popped node is not `null`, add it to the queue.
  • Step 3: Return the `root` node.


Implementation

We can piggyback on the level order traversal implementation we learned earlier to search for the parent node and perform the insertion.

  1. C++

  2. Java

  3. Typescript

  4. Javascript

  5. Python

Complexity Analysis

The iterative level order traversal algorithm uses a queue, so the extra space is linear. Even though this implementation performs better in cases where the recursive algorithm performed worse, it performs worse where it performed best. This is because the entire tree would need to be traversed for a perfect binary tree to find the spot where this new node will be inserted.

The space complexity is directly proportional to the maximum number of nodes in a level, which is 2^H.

Worst case

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

  • Space Complexity - O(1)
  • Time Complexity - O(1)

Worst Case - Perfect Binary Tree

  • Space Complexity - O(2^H)
  • Time Complexity - O(N)
Was this helpful?