Simple Java solution - O(N)

• Simply traverse recursively to the depth d - 1 and add nodes accordingly.

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

private void add(TreeNode node, int v, int d, int currentDepth) {
if (node == null) {
return;
}

if (currentDepth == d - 1) {
TreeNode temp = node.left;
node.left = new TreeNode(v);
node.left.left = temp;

temp = node.right;
node.right = new TreeNode(v);
node.right.right = temp;
return;
}

add(node.left, v, d, currentDepth + 1);
add(node.right, v, d, currentDepth + 1);
}
}

``````

• Almost the same as my solution, except the null check can be put before put a new layer into the stack, in this way, the stack can save a bout half. This is very useful when the tree is very big.

``````public TreeNode addOneRow(TreeNode root, int v, int d) {
if(d == 1) {
TreeNode newRoot = new TreeNode(v);
newRoot.left = root;
return newRoot;
}
return root;
}
private static void addSubNodes(TreeNode root, int v, int d, int p) {
if(d == p) {
TreeNode newLeft = new TreeNode(v);
TreeNode newRight = new TreeNode(v);
newLeft.left = root.left;
root.left = newLeft;
newRight.right = root.right;
root.right = newRight;
return;
}
if(root.left != null)//put null check here to avoid 1/2 stack.
if(root.right != null)
}``````

• @Felomeng
The position of the null checks that you have shown will not save half the stack. It would save 1 call stack entry per null node. At any given time there can be only 1 extra node inserted by my null checks. There will be a total of ~ 2*N extra nodes inserted if there are N' nodes with children = null over the course of the algorithm.
Nonetheless, your checks do save the additional time required to allocate a stack entry for an add call with a null node. Thanks for the insight, really made me think about my solution! :)

• @Felomeng But even if left child is null but the depth matches, new node should be created and its respective left or right child should be set to null. I don't get the reason of checking for null? Or may be i have missed something, Thanks :)

• Thanks for the nice solution! Here is mine in C++.

``````class Solution {
public:
TreeNode* addOneRow(TreeNode* root, int v, int d) {
if (d == 1) {
TreeNode *p = new TreeNode(v);
p->left = root;
return p;
}
dfs(root, v, d-1);
return root;
}
private:
void dfs(TreeNode* p, int v, int d) {
if (p == nullptr) return;
if (d == 1) {
TreeNode *pl = new TreeNode(v), *pr = new TreeNode(v);
pl->left = p->left;
pr->right = p->right;
p->left = pl;
p->right = pr;
}
else {
dfs(p->left, v, d-1);
dfs(p->right, v, d-1);
}
}
};
``````

• This post is deleted!

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.