LeetCode 623: Add One Row to Tree Solution

Master LeetCode problem 623 (Add One Row to Tree), a medium challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

623. Add One Row to Tree

Medium

Tree Depth-First Search Breadth-First Search Binary Tree

Problem Explanation

Explanation

To solve this problem, we can perform a level-order traversal of the binary tree. While traversing each level, we keep track of the depth. When we reach the desired depth, we add the new nodes with the given value as children of the nodes at the current depth - 1. We need to consider the edge case where the depth is 1 separately.

Time complexity: O(n), where n is the number of nodes in the tree
Space complexity: O(n) for the queue used in the level-order traversal

Solution Code

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<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        int currDepth = 1;
        
        while (currDepth < 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);
            }
            currDepth++;
        }
        
        while (!queue.isEmpty()) {
            TreeNode node = queue.poll();
            TreeNode leftNode = new TreeNode(val);
            TreeNode rightNode = new TreeNode(val);
            leftNode.left = node.left;
            rightNode.right = node.right;
            node.left = leftNode;
            node.right = rightNode;
        }
        
        return root;
    }
}

Try It Yourself

Loading code editor...

Frequently Asked Questions

How to solve LeetCode 623 (Add One Row to Tree)?

This page provides optimized solutions for LeetCode problem 623 (Add One Row to Tree) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 623 (Add One Row to Tree)?

The time complexity for LeetCode 623 (Add One Row to Tree) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 623 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 623 in Java, C++, or Python.

Back to LeetCode Solutions