623. Add One Row to Tree

Jump to Solution: Python Java C++ JavaScript C#

Problem Description

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.

Examples:

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, 10⁴]
The depth of the tree is in the range [1, 10⁴]
-100 <= Node.val <= 100
-10⁵ <= val <= 10⁵
1 <= depth <= the depth of tree + 1

Solution

Python Solution

class Solution:
    def addOneRow(self, root: Optional[TreeNode], val: int, depth: int) -> Optional[TreeNode]:
        if depth == 1:
            new_root = TreeNode(val)
            new_root.left = root
            return new_root
        
        def dfs(node: TreeNode, current_depth: int) -> None:
            if not node:
                return
            
            if current_depth == depth - 1:
                # Store original left and right children
                left = node.left
                right = node.right
                
                # Create new nodes with value val
                node.left = TreeNode(val)
                node.right = TreeNode(val)
                
                # Connect original children
                node.left.left = left
                node.right.right = right
            else:
                dfs(node.left, current_depth + 1)
                dfs(node.right, current_depth + 1)
        
        dfs(root, 1)
        return root

Time Complexity: O(N)

Where N is the number of nodes in the tree.

Space Complexity: O(H)

Where H is the height of the tree (recursion stack).

Explanation:

Handle special case when depth = 1
Use DFS to traverse to the correct depth
At target depth - 1, store original children
Create new nodes and connect them properly
Continue DFS for other branches

Java Solution

class Solution {
    public TreeNode addOneRow(TreeNode root, int val, int depth) {
        if (depth == 1) {
            TreeNode newRoot = new TreeNode(val);
            newRoot.left = root;
            return newRoot;
        }
        
        dfs(root, val, depth, 1);
        return root;
    }
    
    private void dfs(TreeNode node, int val, int depth, int currentDepth) {
        if (node == null) {
            return;
        }
        
        if (currentDepth == depth - 1) {
            TreeNode left = node.left;
            TreeNode right = node.right;
            
            node.left = new TreeNode(val);
            node.right = new TreeNode(val);
            
            node.left.left = left;
            node.right.right = right;
        } else {
            dfs(node.left, val, depth, currentDepth + 1);
            dfs(node.right, val, depth, currentDepth + 1);
        }
    }
}

Alternative Solution using BFS:

class Solution {
    public TreeNode addOneRow(TreeNode root, int val, int depth) {
        if (depth == 1) {
            TreeNode newRoot = new TreeNode(val);
            newRoot.left = root;
            return newRoot;
        }
        
        Queue queue = new LinkedList<>();
        queue.offer(root);
        int currentDepth = 1;
        
        while (currentDepth < depth - 1) {
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                TreeNode node = queue.poll();
                if (node.left != null) queue.offer(node.left);
                if (node.right != null) queue.offer(node.right);
            }
            currentDepth++;
        }
        
        while (!queue.isEmpty()) {
            TreeNode node = queue.poll();
            TreeNode left = node.left;
            TreeNode right = node.right;
            
            node.left = new TreeNode(val);
            node.right = new TreeNode(val);
            
            node.left.left = left;
            node.right.right = right;
        }
        
        return root;
    }
}

C++ Solution

class Solution {
public:
    TreeNode* addOneRow(TreeNode* root, int val, int depth) {
        if (depth == 1) {
            TreeNode* newRoot = new TreeNode(val);
            newRoot->left = root;
            return newRoot;
        }
        
        dfs(root, val, depth, 1);
        return root;
    }
    
private:
    void dfs(TreeNode* node, int val, int depth, int currentDepth) {
        if (!node) return;
        
        if (currentDepth == depth - 1) {
            TreeNode* left = node->left;
            TreeNode* right = node->right;
            
            node->left = new TreeNode(val);
            node->right = new TreeNode(val);
            
            node->left->left = left;
            node->right->right = right;
        } else {
            dfs(node->left, val, depth, currentDepth + 1);
            dfs(node->right, val, depth, currentDepth + 1);
        }
    }
};

JavaScript Solution

/**
 * @param {TreeNode} root
 * @param {number} val
 * @param {number} depth
 * @return {TreeNode}
 */
var addOneRow = function(root, val, depth) {
    if (depth === 1) {
        const newRoot = new TreeNode(val);
        newRoot.left = root;
        return newRoot;
    }
    
    function dfs(node, currentDepth) {
        if (!node) return;
        
        if (currentDepth === depth - 1) {
            const left = node.left;
            const right = node.right;
            
            node.left = new TreeNode(val);
            node.right = new TreeNode(val);
            
            node.left.left = left;
            node.right.right = right;
        } else {
            dfs(node.left, currentDepth + 1);
            dfs(node.right, currentDepth + 1);
        }
    }
    
    dfs(root, 1);
    return root;
};

Alternative Solution using Queue:

var addOneRow = function(root, val, depth) {
    if (depth === 1) {
        const newRoot = new TreeNode(val);
        newRoot.left = root;
        return newRoot;
    }
    
    const queue = [root];
    let currentDepth = 1;
    
    while (currentDepth < depth - 1) {
        const size = queue.length;
        for (let i = 0; i < size; i++) {
            const node = queue.shift();
            if (node.left) queue.push(node.left);
            if (node.right) queue.push(node.right);
        }
        currentDepth++;
    }
    
    while (queue.length) {
        const node = queue.shift();
        const left = node.left;
        const right = node.right;
        
        node.left = new TreeNode(val);
        node.right = new TreeNode(val);
        
        node.left.left = left;
        node.right.right = right;
    }
    
    return root;
};

Implementation Comparison:

DFS solution is more space-efficient for deep trees
BFS solution might be more intuitive for level-based operations
Both solutions have the same time complexity
BFS uses more space for wide trees

C# Solution

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left;
 *     public TreeNode right;
 *     public TreeNode(int val=0, TreeNode left=null, TreeNode right=null) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
public class Solution {
    public TreeNode AddOneRow(TreeNode root, int val, int depth) {
        if (depth == 1) {
            var newRoot = new TreeNode(val);
            newRoot.left = root;
            return newRoot;
        }
        
        DFS(root, val, depth, 1);
        return root;
    }
    
    private void DFS(TreeNode node, int val, int depth, int currentDepth) {
        if (node == null) {
            return;
        }
        
        if (currentDepth == depth - 1) {
            TreeNode left = node.left;
            TreeNode right = node.right;
            
            node.left = new TreeNode(val);
            node.right = new TreeNode(val);
            
            node.left.left = left;
            node.right.right = right;
        } else {
            DFS(node.left, val, depth, currentDepth + 1);
            DFS(node.right, val, depth, currentDepth + 1);
        }
    }
}

Alternative Solution using BFS:

public class Solution {
    public TreeNode AddOneRow(TreeNode root, int val, int depth) {
        if (depth == 1) {
            var newRoot = new TreeNode(val);
            newRoot.left = root;
            return newRoot;
        }
        
        var queue = new Queue();
        queue.Enqueue(root);
        int currentDepth = 1;
        
        while (currentDepth < depth - 1) {
            int size = queue.Count;
            for (int i = 0; i < size; i++) {
                var node = queue.Dequeue();
                if (node.left != null) queue.Enqueue(node.left);
                if (node.right != null) queue.Enqueue(node.right);
            }
            currentDepth++;
        }
        
        while (queue.Count > 0) {
            var node = queue.Dequeue();
            TreeNode left = node.left;
            TreeNode right = node.right;
            
            node.left = new TreeNode(val);
            node.right = new TreeNode(val);
            
            node.left.left = left;
            node.right.right = right;
        }
        
        return root;
    }
}

Implementation Notes:

DFS solution is more space-efficient for deep trees
BFS solution might be more intuitive for level-based operations
Both solutions handle the special case of depth=1
Time complexity is O(N) for both solutions