Understanding insertion at root

Insert at root is an operation where we insert a new node with the given value at the root of a given binary tree. The operation is simple as it does not involve any tree traversal and adds links to the existing tree. There are two cases to consider.

1. The tree is empty

If the given tree is empty, we can create a new node with the given value, which becomes the tree itself.

Insert at root in an empty tree

Algorithm

  • Step 1: Create a new node with the given data.
  • Step 2: Return the new node, as this is the new `root`.

2. The tree is not empty

If the tree is not empty, we create a new node and link the existing tree as its left or right subtree. Deciding whether the old tree should be the left or right child of the newly created node is subjective.

Inserting at root in a non empty binary tree

Algorithm

  • Step 1: Create a new node with the given data.
  • Step 2: Set the new node's `left`(or `right`) pointer to hold the reference of the existing `root`.
  • Step 3: Return the new node, as this is the new `root`.

Implementation

Both cases of this operation can be implemented as a simple three-line function.

  1. C++

  2. Java

  3. Typescript

  4. Javascript

  5. Python

Complexity Analysis

Since we are just creating one extra tree node and doing just setting one pointer in the newly created node, both the runtime and space complexity is constant.

Best Case

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

Worst Case

  • Space Complexity - O(1)
  • Time Complexity - O(1)
Was this helpful?