Similar Problems

Similar Problems not available

Add One Row To Tree - Leetcode Solution


LeetCode:  Add One Row To Tree Leetcode Solution

Difficulty: Medium

Topics: binary-tree tree depth-first-search breadth-first-search  

The problem statement can be found here:

Problem Description:

Given the root of a binary tree, then value v and depth d, insert a row of nodes with value v at the given depth d.

The root node is at depth 1.

Example 1: Input: 4 /
2 6 / \ /
3 1 5 7

v = 1, d = 2

Output: 4 /
1 1 / \ /
2 6 5 7 /
3 1

Example 2: Input: 4 /
/ \
3 1

v = 1, d = 3

Output: 4 /
2 /
3 1 / 1


  • Create a recursive function that takes the node, level, the value to be inserted, and the target depth as arguments.

  • Base case:

    • If the current level is one less than the target depth, we need to insert a new row of nodes at this level.
    • Create new nodes with the given value and set their left and right children to be the previous left and right children of the current node.
  • Recursive case:

    • Recursively call the function on the left and right children of the current node if they exist, decrementing the level by one each time.
  • Call the recursive function on the root node with the initial level being 1.

  • Return the modified root node.


class Solution {
    TreeNode* addOneRow(TreeNode* root, int v, int d) {
        if(d == 1){
            // create new root node with v as the value and set its left child as the previous root node
            TreeNode* newRoot = new TreeNode(v);
            newRoot->left = root;
            return newRoot;
        addOneRowDFS(root, 1, v, d);
        return root;
    void addOneRowDFS(TreeNode* node, int level, int v, int d){
        if(node == NULL){
        if(level == d-1){
            // create new left node with v as the value and set its left and right children
            TreeNode* newLeft = new TreeNode(v);
            newLeft->left = node->left;
            node->left = newLeft;
            // create new right node with v as the value and set its left and right children
            TreeNode* newRight = new TreeNode(v);
            newRight->right = node->right;
            node->right = newRight;
            addOneRowDFS(node->left, level+1, v, d);
            addOneRowDFS(node->right, level+1, v, d);

Time Complexity:

Since we are traversing all the nodes in the given tree, the time complexity is O(n), where n is the number of nodes in the tree.

Space Complexity:

The space complexity is O(h), where h is the height of the tree. This is because the recursive function call stack will have at most h elements.

Add One Row To Tree Solution Code