623. Add One Row to Tree LeetCode Solution

In this guide, you will get 623. Add One Row to Tree LeetCode Solution with the best time and space complexity. The solution to Add One Row to Tree problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Problem Statement
Complexity Analysis
Add One Row to Tree solution in C++
Add One Row to Tree solution in Java
Add One Row to Tree solution in Python
Additional Resources

623. Add One Row to Tree LeetCode Solution image

Problem Statement of Add One Row to Tree

Given the root of a binary tree and two integers val and depth, add a row of nodes with value val at the given depth depth.
Note that the root node is at depth 1.
The adding rule is:

Given the integer depth, for each not null tree node cur at the depth depth – 1, create two tree nodes with value val as cur’s left subtree root and right subtree root.
cur’s original left subtree should be the left subtree of the new left subtree root.
cur’s original right subtree should be the right subtree of the new right subtree root.
If depth == 1 that means there is no depth depth – 1 at all, then create a tree node with value val as the new root of the whole original tree, and the original tree is the new root’s left subtree.

Example 1:

Input: root = [4,2,6,3,1,5], val = 1, depth = 2
Output: [4,1,1,2,null,null,6,3,1,5]

Example 2:

Input: root = [4,2,null,3,1], val = 1, depth = 3
Output: [4,2,null,1,1,3,null,null,1]

Constraints:

The number of nodes in the tree is in the range [1, 104].
The depth of the tree is in the range [1, 104].
-100 <= Node.val <= 100
-105 <= val <= 105
1 <= depth <= the depth of tree + 1

Complexity Analysis

Time Complexity: O(n)
Space Complexity: O(n)

623. Add One Row to Tree LeetCode Solution in C++

class Solution {
 public:
  TreeNode* addOneRow(TreeNode* root, int v, int d) {
    if (d == 1) {
      TreeNode* newRoot = new TreeNode(v);
      newRoot->left = root;
      return newRoot;
    }

    int depth = 0;
    queue<TreeNode*> q{{root}};

    while (!q.empty()) {
      ++depth;
      for (int sz = q.size(); sz > 0; --sz) {
        TreeNode* node = q.front();
        q.pop();
        if (node->left)
          q.push(node->left);
        if (node->right)
          q.push(node->right);
        if (depth == d - 1) {
          TreeNode* cachedLeft = node->left;
          TreeNode* cachedRight = node->right;
          node->left = new TreeNode(v);
          node->right = new TreeNode(v);
          node->left->left = cachedLeft;
          node->right->right = cachedRight;
        }
      }
      if (depth == d - 1)
        break;
    }

    return root;
  }
};
/* code provided by PROGIEZ */

623. Add One Row to Tree LeetCode Solution in Java

class Solution {
  public TreeNode addOneRow(TreeNode root, int v, int d) {
    if (d == 1) {
      TreeNode newRoot = new TreeNode(v);
      newRoot.left = root;
      return newRoot;
    }

    int depth = 0;
    Queue<TreeNode> q = new ArrayDeque<>(List.of(root));

    while (!q.isEmpty()) {
      ++depth;
      for (int sz = q.size(); sz > 0; --sz) {
        TreeNode node = q.poll();
        if (node.left != null)
          q.offer(node.left);
        if (node.right != null)
          q.offer(node.right);
        if (depth == d - 1) {
          TreeNode cachedLeft = node.left;
          TreeNode cachedRight = node.right;
          node.left = new TreeNode(v);
          node.right = new TreeNode(v);
          node.left.left = cachedLeft;
          node.right.right = cachedRight;
        }
      }
      if (depth == d - 1)
        break;
    }

    return root;
  }
}
// code provided by PROGIEZ