Modify a Binary Tree by adding a level of nodes with given value at a specified level

0 0 26 minutes read

Given a Binary Tree consisting of N nodes and two integers K and L, the task is to add one row of nodes of value K at the L^th level, such that the orientation of the original tree remains unchanged.

Examples:

Input: K = 1, L = 2

Output:
1
1 1
2 3
4 5 6
Explanation:
Below is the tree after inserting node with value 1 in the K(= 2) th level.

Input: K = 1, L = 1

Output:
1
1
2 3
4 5 6

Approach 1: The given problem can be solved by using Breadth First search for traversal of the tree and adding nodes with a given value between a node at level (L – 1) and roots of its left and right subtree. Follow the steps below to solve the problem:

If L is 1 then make the new node with value K then join the current root to the left of the new node making the new node the root node.
Initialize a Queue, say Q which is used to traverse the tree using BFS.
Initialize a variable, say CurrLevel that stores the current level of a node.
Iterate while Q is not empty() and CurrLevel is less than (L – 1) and perform the following steps:
- Store the size of queue Q in a variable say len.
- Iterate while len is greater than 0 and then pop the front element of the queue and push the left and the right subtree in Q.
- Increment the value of CurrLevel by 1.
Now again iterate while Q is not empty() and perform the following steps:
- Store the front node of Q in a variable say temp and pop the front element.
- Store the left and the right subtree of temp node in variables, say temp1 and temp2 respectively.
- Create a new node with value K and then join the current node to the left of node temp by assigning the node value to temp.left.
- Again create a new node with value K and then join the current node to the right of node temp by assigning the node value to temp.right.
- Then join the temp1 to the left of the new node i.e., temp.left.left and temp2 to the right of the new node i.e., temp.right.right.
After completing the above steps, print the tree in level order traversal.

Below is the implementation of the above approach:

C++

// C++ program for the above approach
#include <bits/stdc++.h>
 
using namespace std;
 
// Class of TreeNode
struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    
  // Constructor
    TreeNode(int v)
    {
        val = v;
        left = right = NULL;
    }
};
 
// Function to add one row to a
// binary tree
TreeNode* addOneRow(TreeNode* root, int val, int depth) {
        queue<TreeNode*> q;
        if(depth==1)
        {
            TreeNode* rt=new TreeNode(val);
            rt->left=root;
            return rt;
        }
        int c=1;
        q.push(root);
        while(!q.empty() && c<depth)
        {
            int a=q.size();
            c++;
            for(int i=0;i<a;i++)
            {
                auto k=q.front();
                q.pop();
                if(c==depth)
                {
                    if(k->left!=nullptr)
                    {
                        TreeNode* tm=new TreeNode(val);
                        TreeNode* t=k->left;
                        k->left=tm;
                        tm->left=t;
                    }
                    else
                    {
                        TreeNode* tm=new TreeNode(val);
                        k->left=tm;
                    }
                     
                    if(k->right!=nullptr)
                    {
                        TreeNode* tm=new TreeNode(val);
                        TreeNode* t=k->right;
                        k->right=tm;
                        tm->right=t;
                    }
                    else{
                        TreeNode* tm=new TreeNode(val);
                        k->right=tm;
                    }
                }
                else
                {
                    if(k->left!=nullptr)
                        q.push(k->left);
                    if(k->right!=nullptr)
                        q.push(k->right);
                }
            }
        }
        return root;
    }
// Function to print the tree in
// the level order traversal
void levelOrder(TreeNode *root)
{
    queue<TreeNode*> Q;
 
    if (root == NULL) {
        cout<<("Null")<<endl;
        return;
    }
 
    // Add root node to Q
    Q.push(root);
 
    while (Q.size() > 0) {
 
        // Stores the total nodes
        // at current level
        int len = Q.size();
 
        // Iterate while len
        // is greater than 0
        while (len > 0) {
 
            // Stores the front Node
            TreeNode *temp = Q.front();
            Q.pop();
 
            // Print the value of
            // the current node
            cout << temp->val << " ";
 
            // If reference to left
            // subtree is not NULL
            if (temp->left != NULL)
 
                // Add root of left
                // subtree to Q
                Q.push(temp->left);
 
            // If reference to right
            // subtree is not NULL
            if (temp->right != NULL)
 
                // Add root of right
                // subtree to Q
                Q.push(temp->right);
 
            // Decrement len by 1
            len--;
        }
 
        cout << endl;
    }
}
 
// Driver Code
int main()
{
   
    // Given Tree
    TreeNode *root = new TreeNode(1);
    root->left = new TreeNode(2);
    root->left->left = new TreeNode(4);
    root->left->right = new TreeNode(5);
    root->right = new TreeNode(3);
    root->right->right = new TreeNode(6);
 
    int L = 2;
    int K = 1;
 
    levelOrder(addOneRow(root, K, L));
}

Java

// Java program for the above approach
import java.util.LinkedList;
import java.util.Queue;
 
public class Main {
    static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
 
        // Constructor
        TreeNode(int v)
        {
            val = v;
            left = right = null;
        }
    }
 
    // Function to add one row to a
    // binary tree
    public static TreeNode addOneRow(TreeNode root, int val,
                                     int depth)
    {
        Queue<TreeNode> q = new LinkedList<>();
        if (depth == 1) {
            TreeNode rt = new TreeNode(val);
            rt.left = root;
            return rt;
        }
        int c = 1;
        q.offer(root);
        while (!q.isEmpty() && c < depth) {
            int a = q.size();
            c++;
            for (int i = 0; i < a; i++) {
                TreeNode k = q.poll();
                if (c == depth) {
                    if (k.left != null) {
                        TreeNode tm = new TreeNode(val);
                        TreeNode t = k.left;
                        k.left = tm;
                        tm.left = t;
                    }
                    else {
                        TreeNode tm = new TreeNode(val);
                        k.left = tm;
                    }
 
                    if (k.right != null) {
                        TreeNode tm = new TreeNode(val);
                        TreeNode t = k.right;
                        k.right = tm;
                        tm.right = t;
                    }
                    else {
                        TreeNode tm = new TreeNode(val);
                        k.right = tm;
                    }
                }
                else {
                    if (k.left != null)
                        q.offer(k.left);
                    if (k.right != null)
                        q.offer(k.right);
                }
            }
        }
        return root;
    }
 
    // Function to print the tree in
    // the level order traversal
    public static void levelOrder(TreeNode root)
    {
        Queue<TreeNode> Q = new LinkedList<>();
 
        if (root == null) {
            System.out.println("Null");
            return;
        }
 
        // Add root node to Q
        Q.offer(root);
 
        while (Q.size() > 0) {
            // Stores the total nodes
            // at current level
            int len = Q.size();
 
            // Iterate while len
            // is greater than 0
            while (len > 0) {
                // Stores the front Node
                TreeNode temp = Q.poll();
 
                // Print the value of
                // the current node
                System.out.print(temp.val + " ");
 
                // If reference to left
                // subtree is not NULL
                if (temp.left != null)
 
                    // Add root of left
                    // subtree to Q
                    Q.offer(temp.left);
 
                // If reference to right
                // subtree is not NULL
                if (temp.right != null)
 
                    // Add root of right
                    // subtree to Q
                    Q.offer(temp.right);
 
                // Decrement len by 1
                len--;
            }
 
            System.out.println();
        }
    }
 
    // Driver Code
    public static void main(String[] args)
    {
        // Given Tree
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(2);
        root.left.left = new TreeNode(4);
        root.left.right = new TreeNode(5);
        root.right = new TreeNode(3);
        root.right.right = new TreeNode(6);
 
        int L = 2;
        int K = 1;
 
        levelOrder(addOneRow(root, K, L));
    }
}

Python3

#Python3 code for the above approach
# Class of TreeNode
class TreeNode:
    def __init__(self, v):
        self.val = v
        self.left = None
        self.right = None
 
 
# Function to add one row to a
# binary tree
 
def addOneRow(root, val, depth):
    q = []
    if depth == 1:
        rt = TreeNode(val)
        rt.left = root
        return rt
    c = 1
    q.append(root)
    while q and c < depth:
        a = len(q)
        c += 1
        for i in range(a):
            k = q[0]
            q.pop(0)
            if c == depth:
                if k.left is not None:
                    tm = TreeNode(val)
                    t = k.left
                    k.left = tm
                    tm.left = t
                else:
                    tm = TreeNode(val)
                    k.left = tm
                if k.right is not None:
                    tm = TreeNode(val)
                    t = k.right
                    k.right = tm
                    tm.right = t
                else:
                    tm = TreeNode(val)
                    k.right = tm
            else:
                if k.left is not None:
                    q.append(k.left)
                if k.right is not None:
                    q.append(k.right)
    return root
 
# Function to print the tree in
# the level order traversal
def levelOrder(root):
    Q = []
 
    if root is None:
        print("Null")
        return
 
    # Add root node to Q
    Q.append(root)
 
    while len(Q) > 0:
        # Stores the total nodes
        # at current level
        len_ = len(Q)
 
        # Iterate while len is greater than 0
        while len_ > 0:
            # Stores the front Node
            temp = Q[0]
            Q.pop(0)
 
            # Print the value of the current node
            print(temp.val, end=" ")
 
            # If reference to left subtree is not None
            if temp.left is not None:
                # Add root of left subtree to Q
                Q.append(temp.left)
 
            # If reference to right subtree is not None
            if temp.right is not None:
                # Add root of right subtree to Q
                Q.append(temp.right)
 
            # Decrement len by 1
            len_ -= 1
        print()
             
 # Driver Code
if __name__ == "__main__":
    # Given Tree
    root = TreeNode(1)
    root.left = TreeNode(2)
    root.left.left = TreeNode(4)
    root.left.right = TreeNode(5)
    root.right = TreeNode(3)
    root.right.right = TreeNode(6)
 
    L = 2
    K = 1
 
    levelOrder(addOneRow(root, K, L))
#This code is contributed by Potta Lokesh

C#

using System;
using System.Collections.Generic;
 
public class MainClass
{
    public class TreeNode
    {
        public int val;
        public TreeNode left;
        public TreeNode right;
 
        // Constructor
        public TreeNode(int v)
        {
            val = v;
            left = right = null;
        }
    }
 
    // Function to add one row to a binary tree
    public static TreeNode AddOneRow(TreeNode root, int val, int depth)
    {
        Queue<TreeNode> q = new Queue<TreeNode>();
        if (depth == 1)
        {
            TreeNode rt = new TreeNode(val);
            rt.left = root;
            return rt;
        }
        int c = 1;
        q.Enqueue(root);
        while (q.Count > 0 && c < depth)
        {
            int a = q.Count;
            c++;
            for (int i = 0; i < a; i++)
            {
                TreeNode k = q.Dequeue();
                if (c == depth)
                {
                    if (k.left != null)
                    {
                        TreeNode tm = new TreeNode(val);
                        TreeNode t = k.left;
                        k.left = tm;
                        tm.left = t;
                    }
                    else
                    {
                        TreeNode tm = new TreeNode(val);
                        k.left = tm;
                    }
 
                    if (k.right != null)
                    {
                        TreeNode tm = new TreeNode(val);
                        TreeNode t = k.right;
                        k.right = tm;
                        tm.right = t;
                    }
                    else
                    {
                        TreeNode tm = new TreeNode(val);
                        k.right = tm;
                    }
                }
                else
                {
                    if (k.left != null)
                        q.Enqueue(k.left);
                    if (k.right != null)
                        q.Enqueue(k.right);
                }
            }
        }
        return root;
    }
 
    // Function to print the tree in the level order traversal
    public static void LevelOrder(TreeNode root)
    {
        Queue<TreeNode> Q = new Queue<TreeNode>();
 
        if (root == null)
        {
            Console.WriteLine("Null");
            return;
        }
 
        // Add root node to Q
        Q.Enqueue(root);
 
        while (Q.Count > 0)
        {
            // Stores the total nodes at current level
            int len = Q.Count;
 
            // Iterate while len is greater than 0
            while (len > 0)
            {
                // Stores the front Node
                TreeNode temp = Q.Dequeue();
 
                // Print the value of the current node
                Console.Write(temp.val + " ");
 
                // If reference to left subtree is not NULL
                if (temp.left != null)
 
                    // Add root of left subtree to Q
                    Q.Enqueue(temp.left);
 
                // If reference to right subtree is not NULL
                if (temp.right != null)
 
                    // Add root of right subtree to Q
                    Q.Enqueue(temp.right);
 
                // Decrement len by 1
                len--;
            }
 
            Console.WriteLine();
        }
    }
 
    // Driver Code
    public static void Main()
    {
        // Given Tree
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(2);
        root.left.left = new TreeNode(4);
        root.left.right = new TreeNode(5);
        root.right = new TreeNode(3);
        root.right.right = new TreeNode(6);
 
        int L = 2;
        int K = 1;
 
        LevelOrder(AddOneRow(root, K, L));
    }
}

Javascript

// JavaScript program for the above approach
// class of TreeNode
class TreeNode{
    constructor(v){
        this.val = v;
        this.left = null;
        this.right = null;
    }
}
 
// function to add one row to a binary tree
function addOneRow(root, val, depth){
    q = [];
    if(depth == 1){
        let rt = new TreeNode(val);
        rt.left = root;
        return rt;
    }
    let c = 1;
    q.push(root);
    while(q.length > 0 && c < depth){
        let a = q.length;
        c++;
        for(let i = 0; i<a; i++){
            let k = q.shift();
            if(c == depth){
                if(k.left != null){
                    let tm = new TreeNode(val);
                    let t = k.left;
                    k.left = tm;
                    tm.left = t;
                }
                else{
                    let tm = new TreeNode(val);
                    k.left = tm;
                }
                 
                if(k.right != null){
                    let tm = new TreeNode(val);
                    let t = k.right;
                    k.right = tm;
                    tm.right = t;
                }
                else{
                    let tm = new TreeNode(val);
                    k.right = tm;
                }
            }
            else{
                if(k.left != null)
                    q.push(k.left);
                if(k.right != null)
                    q.push(k.right);
            }
        }
    }
    return root;
}
 
// function to print the tree in
// the level order traversal
function levelOrder(root)
{
    Q = [];
    if(root == null){
        console.log("NULL");
        return;
    }
     
    // add root node to Q
    Q.push(root);
    while(Q.length > 0)
    {
     
        // stores the total nodes
        // at current level
        let len = Q.length;
         
        // iterate while len is greater than 0
        while(len > 0)
        {
         
            // stores the front node
            let temp = Q.shift();
             
            // print the value of the current node
            console.log(temp.val + " ");
             
            // if reference to left subtree is not null
            if(temp.left != null)
            {
             
                // add root of right subtree to Q
                Q.push(temp.left);
            }
             
            // if reference to right subtree is not null
            if(temp.right != null)
            {
             
                // add root of right subtree to Q
                Q.push(temp.right);
            }
             
            // decrement len by 1
            len--;
        }
         
    }
}
 
// driver code
let root = new TreeNode(1);
root.left = new TreeNode(2);
root.left.left = new TreeNode(4);
root.left.right = new TreeNode(5);
root.right = new TreeNode(3);
root.right.right = new TreeNode(6);
 
let L = 2;
let K = 1;
 
levelOrder(addOneRow(root, K, L));
 
// This code is contributed by Yash Agarwal(yashagarwal2852002)

Output

Time Complexity: O(N)
Auxiliary Space: O(N)

Approach 2: The given problem can also be solved by using Depth First search for traversal of the tree and adding nodes with a given value between a node at level (L – 1) and roots of its left and right subtree. Follow the steps below to solve the problem:

If L is 1 then make the new node with value K then join the current root to the left of the new node making the new node the root node.
Make the initial DFS call for root node by passing the current level equal to 1.
Check if the current level is equal to desired depth minus one, that is if it is one level before the desired level L (depth is equal to L-1) then:
- Create a node tmp with val K and make tmp.left = cur.left and cur.left = tmp.
- Create a node tmp with val K and make tmp.right = cur.right and cur.right= tmp.
Make recursive dfs calls for left and right subtree by incrementing the level by 1.
Print the tree in level order traversal.

Below is the implementation of the above approach:

C++

// C++ program for the above approach
#include <bits/stdc++.h>
  
using namespace std;
  
// Class of TreeNode
struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
     
  // Constructor
    TreeNode(int v)
    {
        val = v;
        left = right = NULL;
    }
};
  
void dfsUtil(TreeNode* root, int level, int L, int K){
    // base condition
    if(root==NULL)
        return;
 
    // when the parent of desired level 
    // is reached in traversal
   
    if(level == L-1){
        // Create a new Node tmp with
        // value K and assign its left 
        // to root.left and root.left to tmp
        TreeNode* tmp = new TreeNode(K);
        tmp->left = root->left;
        root->left = tmp;
 
        // Create another Node tmp1 with
        // value K and assign its left 
        // to root.left and root.left to tmp
 
        TreeNode* tmp1 = new TreeNode(K);
        tmp1->right = root->right;
        root->right = tmp1;
         
        return;
    }
    /// make the recursive calls
    // for left and right subtree by increasing level by 1
    dfsUtil(root->left, level+1, L, K);
    dfsUtil(root->right, level+1, L, K);
}
 
// Function to add one row to a
// binary tree
TreeNode* addOneRow(TreeNode* root, int K, int L) {
     
    // If L is 1
    if (L == 1) {
  
        // Store the node having
        // the value K
        TreeNode *t = new TreeNode(K);
  
        // Join node t with the
        // root node
        t->left = root;
        return t;
    }
    // Call dfs with val, depth and current level as 1 
    // for traversing and adding the nodes with 
    // given value at given level
    dfsUtil(root, 1, L, K);
     
    return root;
}
 
// Function to print the tree in
// the level order traversal
void levelOrder(TreeNode *root)
{
    queue<TreeNode*> Q;
  
    if (root == NULL) {
        cout<<("Null")<<endl;
        return;
    }
  
    // Add root node to Q
    Q.push(root);
  
    while (Q.size() > 0) {
  
        // Stores the total nodes
        // at current level
        int len = Q.size();
  
        // Iterate while len
        // is greater than 0
        while (len > 0) {
  
            // Stores the front Node
            TreeNode *temp = Q.front();
            Q.pop();
  
            // Print the value of
            // the current node
            cout << temp->val << " ";
  
            // If reference to left
            // subtree is not NULL
            if (temp->left != NULL)
  
                // Add root of left
                // subtree to Q
                Q.push(temp->left);
  
            // If reference to right
            // subtree is not NULL
            if (temp->right != NULL)
  
                // Add root of right
                // subtree to Q
                Q.push(temp->right);
  
            // Decrement len by 1
            len--;
        }
  
        cout << endl;
    }
}
 
// Driver Code
int main()
{
    // Given Tree
    TreeNode *root = new TreeNode(1);
    root->left = new TreeNode(2);
    root->left->left = new TreeNode(4);
    root->left->right = new TreeNode(5);
    root->right = new TreeNode(3);
    root->right->right = new TreeNode(6);
  
    int L = 2;
    int K = 1;
  
    levelOrder(addOneRow(root, K, L));
}

Java

import java.util.*;
// Class of TreeNode
class TreeNode
{
  int val;
  TreeNode left, right;
 
  // Constructor
  public TreeNode(int v)
  {
    val = v;
    left = right = null;
  }
}
 
class GfG
{
  public static void dfsUtil(TreeNode root, int level, int L, int K)
  {
    // base condition
    if (root == null)
    {
      return;
    }
 
    // when the parent of desired level 
    // is reached in traversal
 
    if (level == L - 1)
    {
      // Create a new Node tmp with
      // value K and assign its left 
      // to root.left and root.left to tmp
      TreeNode tmp = new TreeNode(K);
      tmp.left = root.left;
      root.left = tmp;
 
      // Create another Node tmp1 with
      // value K and assign its left 
      // to root.left and root.left to tmp
 
      TreeNode tmp1 = new TreeNode(K);
      tmp1.right = root.right;
      root.right = tmp1;
 
      return;
    }
    /// make the recursive calls
    // for left and right subtree by increasing level by 1
    dfsUtil(root.left, level + 1, L, K);
    dfsUtil(root.right, level + 1, L, K);
  }
 
  // Function to add one row to a
  // binary tree
  public static TreeNode addOneRow(TreeNode root, int K, int L)
  {
 
    // If L is 1
    if (L == 1)
    {
 
      // Store the node having
      // the value K
      TreeNode t = new TreeNode(K);
 
      // Join node t with the
      // root node
      t.left = root;
      return t;
    }
    // Call dfs with val, depth and current level as 1 
    // for traversing and adding the nodes with 
    // given value at given level
    dfsUtil(root, 1, L, K);
 
    return root;
  }
 
  // Function to print the tree in
  // the level order traversal
  public static void levelOrder(TreeNode root)
  {
    LinkedList<TreeNode> Q = new LinkedList<TreeNode>();
 
    if (root == null)
    {
      System.out.print(("Null"));
      System.out.print("\n");
      return;
    }
 
    // Add root node to Q
    Q.offer(root);
 
    while (Q.size() > 0)
    {
 
      // Stores the total nodes
      // at current level
      int len = Q.size();
 
      // Iterate while len
      // is greater than 0
      while (len > 0)
      {
 
        // Stores the front Node
        TreeNode temp = Q.peek();
        Q.poll();
 
        // Print the value of
        // the current node
        System.out.print(temp.val);
        System.out.print(" ");
 
        // If reference to left
        // subtree is not NULL
        if (temp.left != null)
        {
 
          // Add root of left
          // subtree to Q
          Q.offer(temp.left);
        }
 
        // If reference to right
        // subtree is not NULL
        if (temp.right != null)
        {
 
          // Add root of right
          // subtree to Q
          Q.offer(temp.right);
        }
 
        // Decrement len by 1
        len--;
      }
 
      System.out.print("\n");
    }
  }
 
  // Driver Code
  public static void main(String[] args)
  {
    // Given Tree
    TreeNode root = new TreeNode(1);
    root.left = new TreeNode(2);
    root.left.left = new TreeNode(4);
    root.left.right = new TreeNode(5);
    root.right = new TreeNode(3);
    root.right.right = new TreeNode(6);
 
    int L = 2;
    int K = 1;
 
    levelOrder(addOneRow(root, K, L));
  }
}
 
// This code is contributed by ajaymakvana.

Python3

# Python3 program for the above approach
 
class TreeNode:
    def __init__(self, v):
        self.val = v
        self.left = None
        self.right = None
 
 
def dfs_util(root, level, L, K):
    # base condition
    if root is None:
        return
 
    # when the parent of desired level
    # is reached in traversal
 
    if level == L - 1:
        # Create a new Node tmp with
        # value K and assign its left
        # to root.left and root.left to tmp
        tmp = TreeNode(K)
        tmp.left = root.left
        root.left = tmp
 
        # Create another Node tmp1 with
        # value K and assign its left
        # to root.left and root.left to tmp
 
        tmp1 = TreeNode(K)
        tmp1.right = root.right
        root.right = tmp1
 
        return
 
    # make the recursive calls
    # for left and right subtree by increasing level by 1
    dfs_util(root.left, level + 1, L, K)
    dfs_util(root.right, level + 1, L, K)
 
 
# Function to add one row to a
# binary tree
def add_one_row(root, K, L):
 
    # If L is 1
    if L == 1:
        # Store the node having
        # the value K
        t = TreeNode(K)
 
        # Join node t with the
        # root node
        t.left = root
        return t
 
    # Call dfs with val, depth and current level as 1
    # for traversing and adding the nodes with
    # given value at given level
    dfs_util(root, 1, L, K)
 
    return root
 
 
# Function to print the tree in
# the level order traversal
def level_order(root):
    Q = []
 
    if root is None:
        print("Null")
        return
 
    # Add root node to Q
    Q.append(root)
 
    while len(Q) > 0:
        # Stores the total nodes
        # at current level
        len_ = len(Q)
 
        # Iterate while len
        # is greater than 0
        while len_ > 0:
            # Stores the front Node
            temp = Q.pop(0)
 
            # Print the value of
            # the current node
            print(temp.val, end=' ')
 
            # If reference to left
            # subtree is not NULL
            if temp.left is not None:
 
                # Add root of left
                # subtree to Q
                Q.append(temp.left)
 
            # If reference to right
            # subtree is not NULL
            if temp.right is not None:
 
                # Add root of right
                # subtree to Q
                Q.append(temp.right)
 
            # Decrement len by 1
            len_ -= 1
 
        print()
 
 
# Driver Code
# Given Tree
root = TreeNode(1)
root.left = TreeNode(2)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)
root.right = TreeNode(3)
root.right.right = TreeNode(6);
 
L = 2;
K = 1;
 
level_order(add_one_row(root, K, L));

C#

using System;
using System.Collections.Generic;
 
// Class of TreeNode
public class TreeNode {
    public int val;
    public TreeNode left;
    public TreeNode right;
    // Constructor
    public TreeNode(int v)
    {
        val = v;
        left = right = null;
    }
}
 
public class Solution {
    public void dfsUtil(TreeNode root, int level, int L,
                        int K)
    {
        // base condition
        if (root == null) {
            return;
        }
        // when the parent of desired level
        // is reached in traversal
        if (level == L - 1) {
            // Create a new Node tmp with
            // value K and assign its left
            // to root.left and root.left to tmp
            TreeNode tmp = new TreeNode(K);
            tmp.left = root.left;
            root.left = tmp;
            // Create another Node tmp1 with
            // value K and assign its left
            // to root.left and root.left to tmp
            TreeNode tmp1 = new TreeNode(K);
            tmp1.right = root.right;
            root.right = tmp1;
            return;
        }
        /// make the recursive calls
        // for left and right subtree by increasing level by
        // 1
        dfsUtil(root.left, level + 1, L, K);
        dfsUtil(root.right, level + 1, L, K);
    }
    // Function to add one row to a
    // binary tree
    public TreeNode AddOneRow(TreeNode root, int K, int L)
    {
        // If L is 1
        if (L == 1) {
            // Store the node having
            // the value K
            TreeNode t = new TreeNode(K);
            // Join node t with the
            // root node
            t.left = root;
            return t;
        }
        // Call dfs with val, depth and current level as 1
        // for traversing and adding the nodes with
        // given value at given level
        dfsUtil(root, 1, L, K);
        return root;
    }
    // Function to print the tree in
    // the level order traversal
    public void LevelOrder(TreeNode root)
    {
        Queue<TreeNode> Q = new Queue<TreeNode>();
 
        if (root == null) {
            Console.WriteLine("Null");
            return;
        }
        // Add root node to Q
        Q.Enqueue(root);
 
        while (Q.Count > 0) {
            // Stores the total nodes
            // at current level
            int len = Q.Count;
            // Iterate while len
            // is greater than 0
            while (len > 0) {
                // Stores the front Node
                TreeNode temp = Q.Dequeue();
                Console.Write(temp.val + " ");
                // Print the value of
                // the current node
                if (temp.left != null) {
                    // If reference to right
                    // subtree is not NULL
                    Q.Enqueue(temp.left);
                }
 
                if (temp.right != null) {
                    // Add root of right
                    // subtree to Q
                    Q.Enqueue(temp.right);
                }
 
                len--;
            }
 
            Console.WriteLine();
        }
    }
 
    public static void Main()
    {
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(2);
        root.left.left = new TreeNode(4);
        root.left.right = new TreeNode(5);
        root.right = new TreeNode(3);
        root.right.right = new TreeNode(6);
 
        int L = 2;
        int K = 1;
 
        Solution s = new Solution();
        s.LevelOrder(s.AddOneRow(root, K, L));
    }
}

Javascript

// JavaScript program for the above approach
class TreeNode {
    constructor(v) {
        this.val = v;
        this.left = null;
        this.right = null;
    }
}
 
function dfsUtil(root, level, L, K) {
    // base condition
    if (root == null)
        return;
 
    // when the parent of desired level
    // is reached in traversal
 
    if (level == L - 1) {
        // Create a new Node tmp with
        // value K and assign its left
        // to root.left and root.left to tmp
        let tmp = new TreeNode(K);
        tmp.left = root.left;
        root.left = tmp;
 
        // Create another Node tmp1 with
        // value K and assign its left
        // to root.left and root.left to tmp
 
        let tmp1 = new TreeNode(K);
        tmp1.right = root.right;
        root.right = tmp1;
 
        return;
    }
    /// make the recursive calls
    // for left and right subtree by increasing level by 1
    dfsUtil(root.left, level + 1, L, K);
    dfsUtil(root.right, level + 1, L, K);
}
 
// Function to add one row to a
// binary tree
function addOneRow(root, K, L) {
 
    // If L is 1
    if (L == 1) {
 
        // Store the node having
        // the value K
        let t = new TreeNode(K);
 
        // Join node t with the
        // root node
        t.left = root;
        return t;
    }
    // Call dfs with val, depth and current level as 1
    // for traversing and adding the nodes with
    // given value at given level
    dfsUtil(root, 1, L, K);
 
    return root;
}
 
// Function to print the tree in
// the level order traversal
function levelOrder(root) {
    let Q = [];
 
    if (root == null) {
        console.log("Null");
        return;
    }
 
    // Add root node to Q
    Q.push(root);
 
    while (Q.length > 0) {
 
        // Stores the total nodes
        // at current level
        let len = Q.length;
 
        // Iterate while len
        // is greater than 0
        while (len > 0) {
 
            // Stores the front Node
            let temp = Q.shift();
 
            // Print the value of
            // the current node
            console.log(temp.val + " ");
 
            // If reference to left
            // subtree is not NULL
            if (temp.left != null)
 
                // Add root of left
                // subtree to Q
                Q.push(temp.left);
 
            // If reference to right
            // subtree is not NULL
            if (temp.right != null)
 
                // Add root of right
                // subtree to Q
                Q.push(temp.right);
 
            // Decrement len by 1
            len--;
        }
 
        console.log("\n");
    }
}
 
// Driver Code
// Given Tree
let root = new TreeNode(1);
root.left = new TreeNode(2);
root.left.left = new TreeNode(4);
root.left.right = new TreeNode(5);
root.right = new TreeNode(3);
root.right.right = new TreeNode(6);
 
let L = 2;
let K = 1;
 
levelOrder(addOneRow(root, K, L));
 
// This code contributed by adityamaharshi21

Output

Time Complexity: O(N)
Auxiliary Space: O(N)

Approach 3:

Using the stack.

C++14

#include <bits/stdc++.h>
 
using namespace std;
 
// Class of TreeNode
struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
 
    // Constructor
    TreeNode(int v)
    {
        val = v;
        left = right = NULL;
    }
};
TreeNode* addOneRow(TreeNode* root, int val, int depth)
{
    // if depth is 1
    if (depth == 1) {
        // store the node having
        // the value val
        TreeNode* rt = new TreeNode(val);
        // join node rt with the
        // root node
        rt->left = root;
        return rt;
    }
    else {
        // declare a stack of pair which will be storing
        // the node and its respective level
        stack<pair<TreeNode*, int> > st;
        // push the root node and the level
        st.push(make_pair(root, 1));
        // repeat the process while the stack is not empty
        while (!st.empty()) {
            auto node = st.top().first;
            auto level = st.top().second;
            st.pop();
            // if the node is nullptr then continue
            if (!node)
                continue;
            // if level is equal to the depth-1 then
            if (level == depth - 1) {
                // make a node with the value and make the
                // connections
                TreeNode* t = new TreeNode(val);
                t->left = node->left;
                node->left = t;
                // make a node with the value and make the
                // connections
                TreeNode* p = new TreeNode(val);
                p->right = node->right;
                node->right = p;
                continue;
            }
            // push the node's left and node's right and
            // there level in the stack correspondingly
            st.push(make_pair(node->left, level + 1));
            st.push(make_pair(node->right, level + 1));
        }
    }
    // return the updated root
    return root;
}
// Function to print the tree in
// the level order traversal
 
void levelOrder(TreeNode* root)
{
    queue<TreeNode*> Q;
    if (root == NULL) {
        cout << ("Null") << endl;
        return;
    }
    Q.push(root);
 
    while (Q.size() > 0) {
        int len = Q.size();
        while (len > 0) {
            TreeNode* temp = Q.front();
            Q.pop();
            cout << temp->val << " ";
            if (temp->left != NULL)
                Q.push(temp->left);
            if (temp->right != NULL)
                Q.push(temp->right);
            len--;
        }
        cout << endl;
    }
}
// Driver Code
int main()
{
    TreeNode* root = new TreeNode(1);
    root->left = new TreeNode(2);
    root->left->left = new TreeNode(4);
    root->left->right = new TreeNode(5);
    root->right = new TreeNode(3);
    root->right->right = new TreeNode(6);
    int L = 2;
    int K = 1;
    levelOrder(addOneRow(root, K, L));
}

Java

import com.sun.source.tree.Tree;
 
import java.util.*;
class Pair
{
    TreeNode first;
    Integer second;
    Pair(TreeNode first,Integer second)
    {
        this.first = first;
        this.second = second;
    }
}
// Class of TreeNode
class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
 
    // Constructor
    TreeNode(int v) {
        val = v;
        left = right = null;
    }
}
 
class Main {
    public static TreeNode addOneRow(TreeNode root, int val, int depth) {
        // if depth is 1
        if (depth == 1) {
            // store the node having the value val
            TreeNode rt = new TreeNode(val);
            // join node rt with the root node
            rt.left = root;
            return rt;
        } else {
            // declare a stack of pair which will be storing
            // the node and its respective level
            Stack<Pair> st = new Stack<>();
            // push the root node and the level
            st.push(new Pair(root, 1));
            // repeat the process while the stack is not empty
            while (!st.empty()) {
                Pair pair = st.pop();
                TreeNode node = pair.first;
                int level = pair.second;
                // if the node is null then continue
                if (node == null)
                    continue;
                // if level is equal to the depth-1 then
                if (level == depth - 1) {
                    // make a node with the value and make the
                    // connections
                    TreeNode t = new TreeNode(val);
                    t.left = node.left;
                    node.left = t;
                    // make a node with the value and make the
                    // connections
                    TreeNode p = new TreeNode(val);
                    p.right = node.right;
                    node.right = p;
                    continue;
                }
                // push the node's left and node's right and
                // their level in the stack correspondingly
                st.push(new Pair(node.left, level + 1));
                st.push(new Pair(node.right, level + 1));
            }
        }
        // return the updated root
        return root;
    }
 
    // Function to print the tree in the level order traversal
    public static void levelOrder(TreeNode root) {
        Queue<TreeNode> Q = new LinkedList<>();
        if (root == null) {
            System.out.println("Null");
            return;
        }
        Q.add(root);
 
        while (!Q.isEmpty()) {
            int len = Q.size();
            while (len > 0) {
                TreeNode temp = Q.poll();
                System.out.print(temp.val + " ");
                if (temp.left != null)
                    Q.add(temp.left);
                if (temp.right != null)
                    Q.add(temp.right);
                len--;
            }
            System.out.println();
        }
    }
 
    // Driver Code
    public static void main(String[] args) {
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(2);
        root.left.left = new TreeNode(4);
        root.left.right = new TreeNode(5);
        root.right = new TreeNode(3);
        root.right.right = new TreeNode(6);
        int L = 2;
        int K = 1;
        levelOrder(addOneRow(root, K, L));
    }
}

Python3

# Class of TreeNode
class TreeNode:
    def __init__(self, v):
        self.val = v
        self.left = None
        self.right = None
 
def addOneRow(root, val, depth):
    # if depth is 1
    if depth == 1:
        # store the node having
        # the value val
        rt = TreeNode(val)
        # join node rt with the
        # root node
        rt.left = root
        return rt
    else:
        # declare a stack of pair which will be storing
        # the node and its respective level
        st = []
        # push the root node and the level
        st.append((root, 1))
        # repeat the process while the stack is not empty
        while st:
            node, level = st.pop()
            # if the node is None then continue
            if not node:
                continue
            # if level is equal to the depth-1 then
            if level == depth - 1:
                # make a node with the value and make the
                # connections
                t = TreeNode(val)
                t.left = node.left
                node.left = t
                # make a node with the value and make the
                # connections
                p = TreeNode(val)
                p.right = node.right
                node.right = p
                continue
            # push the node's left and node's right and
            # their level in the stack correspondingly
            st.append((node.left, level + 1))
            st.append((node.right, level + 1))
    # return the updated root
    return root
 
# Function to print the tree in
# the level order traversal
def levelOrder(root):
    if not root:
        print("Null")
        return
    Q = []
    Q.append(root)
    while Q:
        len_Q = len(Q)
        while len_Q > 0:
            temp = Q.pop(0)
            print(temp.val, end=' ')
            if temp.left:
                Q.append(temp.left)
            if temp.right:
                Q.append(temp.right)
            len_Q -= 1
        print()
 
# Driver Code
if __name__ == '__main__':
    root = TreeNode(1)
    root.left = TreeNode(2)
    root.left.left = TreeNode(4)
    root.left.right = TreeNode(5)
    root.right = TreeNode(3)
    root.right.right = TreeNode(6)
    L = 2
    K = 1
    levelOrder(addOneRow(root, K, L))

C#

using System;
using System.Collections.Generic;
 
// Class of TreeNode
public class TreeNode {
  public int val;
  public TreeNode left;
  public TreeNode right;
 
  // Constructor
  public TreeNode(int v)
  {
    val = v;
    left = right = null;
  }
}
 
public class Solution {
  public static TreeNode AddOneRow(TreeNode root, int val,
                                   int depth)
  {
    // if depth is 1
    if (depth == 1) {
       
      // store the node having
      // the value val
      TreeNode rt = new TreeNode(val);
       
      // join node rt with the
      // root node
      rt.left = root;
      return rt;
    }
    else
    {
       
      // declare a stack of pair which will be storing
      // the node and its respective level
      Stack<(TreeNode, int)> st
        = new Stack<(TreeNode, int)>();
       
      // push the root node and the level
      st.Push((root, 1));
       
      // repeat the process while the stack is not
      // empty
      while (st.Count > 0) {
        var(node, level) = st.Pop();
         
        // if the node is null then continue
        if (node == null)
          continue;
         
        // if level is equal to the depth-1 then
        if (level == depth - 1) {
           
          // make a node with the value and make
          // the connections
          TreeNode t = new TreeNode(val);
          t.left = node.left;
          node.left = t;
           
          // make a node with the value and make
          // the connections
          TreeNode p = new TreeNode(val);
          p.right = node.right;
          node.right = p;
          continue;
        }
        // push the node's left and node's right and
        // their level in the stack correspondingly
        st.Push((node.left, level + 1));
        st.Push((node.right, level + 1));
      }
    }
    // return the updated root
    return root;
  }
 
  // Function to print the tree in
  // the level order traversal
  public static void LevelOrder(TreeNode root)
  {
    Queue<TreeNode> Q = new Queue<TreeNode>();
    if (root == null) {
      Console.WriteLine("Null");
      return;
    }
    Q.Enqueue(root);
 
    while (Q.Count > 0) {
      int len = Q.Count;
      while (len > 0) {
        TreeNode temp = Q.Dequeue();
        Console.Write(temp.val + " ");
        if (temp.left != null)
          Q.Enqueue(temp.left);
        if (temp.right != null)
          Q.Enqueue(temp.right);
        len--;
      }
      Console.WriteLine();
    }
  }
 
  // Driver Code
  public static void Main(string[] args)
  {
    TreeNode root = new TreeNode(1);
    root.left = new TreeNode(2);
    root.left.left = new TreeNode(4);
    root.left.right = new TreeNode(5);
    root.right = new TreeNode(3);
    root.right.right = new TreeNode(6);
    int L = 2;
    int K = 1;
    LevelOrder(AddOneRow(root, K, L));
  }
}
 
// This code is contributed by Prajwal Kandekar

Javascript

// Class of TreeNode
class TreeNode {
  constructor(val) {
    this.val = val;
    this.left = null;
    this.right = null;
  }
}
 
function addOneRow(root, val, depth) {
  // if depth is 1
  if (depth === 1) {
    // store the node having
    // the value val
    const rt = new TreeNode(val);
    // join node rt with the
    // root node
    rt.left = root;
    return rt;
  } else {
    // declare a queue which will be storing
    // the node and its respective level
    const q = [];
    // push the root node and the level
    q.push([root, 1]);
    // repeat the process while the queue is not empty
    while (q.length > 0) {
      const [node, level] = q.shift();
      // if the node is null then continue
      if (!node) continue;
      // if level is equal to the depth-1 then
      if (level === depth - 1) {
        // make a node with the value and make the
        // connections
        const t = new TreeNode(val);
        t.left = node.left;
        node.left = t;
        // make a node with the value and make the
        // connections
        const p = new TreeNode(val);
        p.right = node.right;
        node.right = p;
        continue;
      }
      // push the node's left and node's right and
      // their level in the queue correspondingly
      q.push([node.left, level + 1]);
      q.push([node.right, level + 1]);
    }
  }
  // return the updated root
  return root;
}
 
// Function to print the tree in
// the level order traversal
function levelOrder(root) {
  const q = [];
  if (root == null) {
    console.log("Null");
    return;
  }
  q.push(root);
 
  while (q.length > 0) {
    const len = q.length;
    let level = '';
    for (let i = 0; i < len; i++) {
      const temp = q.shift();
      level += temp.val + ' ';
      if (temp.left != null) q.push(temp.left);
      if (temp.right != null) q.push(temp.right);
    }
    console.log(level);
  }
}
 
// Driver Code
const root = new TreeNode(1);
root.left = new TreeNode(2);
root.left.left = new TreeNode(4);
root.left.right = new TreeNode(5);
root.right = new TreeNode(3);
root.right.right = new TreeNode(6);
 
const L = 2;
const K = 1;
levelOrder(addOneRow(root, K, L));

Output

Time Complexity: O(N)
Auxiliary Space: O(N)

Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!