Given the root of a binary tree, then value v and depth d, you need to add a row of nodes with value v at the given depth d. The root node is at depth 1. 

The adding rule is: given a positive integer depth d, for each NOT null tree nodes N in depth d-1, create two tree nodes with value v as N's left subtree root and right subtree root. And N's original left subtree should be the left subtree of the new left subtree root, its original right subtree should be the right subtree of the new right subtree root. If depth d is 1 that means there is no depth d-1 at all, then create a tree node with value v as the new root of the whole original tree, and the original tree is the new root's left subtree.

Example 1:

Input: 
A binary tree as following:
       4
     /   \
    2     6
   / \   / 
  3   1 5   

v = 1

d = 2

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





Example 2:

Input: 
A binary tree as following:
      4
     /   
    2    
   / \   
  3   1    

v = 1

d = 3

Output: 
      4
     /   
    2
   / \    
  1   1
 /     \  
3       1



Note:

The given d is in range [1, maximum depth of the given tree + 1].
The given binary tree has at least one tree node.

Difficulty: MEDIUM_HARD
Tags: Tree algorithms

Graph traversal

Starter code:
# Definition for a binary tree node.
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
    self.val = val
    self.left = left
    self.right = right
class Solution:
    def addOneRow(self, root: TreeNode, v: int, d: int) -> TreeNode:
        

Solutions:
class Solution:

	def addOneRow(self, root, v, d):
		if root:
			if d == 1:
				new_root = TreeNode(v)
				new_root.left = root
				return new_root
			queue = [root]
			level = 1
			while queue and level < d:
				row = []
				for i in range(len(queue)):
					node = queue.pop(0)
					if level == d - 1:
						row.append(node)
					if node.left:
						queue.append(node.left)
					if node.right:
						queue.append(node.right)
				level += 1
			for node in row:
				old = node.left
				node.left = TreeNode(v)
				node.left.left = old
				old = node.right
				node.right = TreeNode(v)
				node.right.right = old
		return root


class Solution:

	def addOneRow(self, root, v, d):
		if d == 1:
			newroot = TreeNode(v)
			newroot.left = root
			return newroot
		queue = [(root, 1)]
		for (node, level) in queue:
			if node.left:
				queue.append((node.left, level + 1))
			if node.right:
				queue.append((node.right, level + 1))
			if level == d - 1:
				newleft = TreeNode(v)
				newleft.left = node.left
				newright = TreeNode(v)
				newright.right = node.right
				node.left = newleft
				node.right = newright
		return root


class Solution:

	def traverse_left(self, stack, node, node_depth, d):
		while node_depth + 1 < d and node.left is not None:
			stack.append((node.left, node_depth + 1))
			node = node.left
			node_depth += 1

	def addOneRow(self, root, v, d):
		if d == 1:
			new_root = TreeNode(v)
			new_root.left = root
			return new_root
		stack = [(root, 1)]
		self.traverse_left(stack, root, 1, d)
		while not not stack:
			(node, node_depth) = stack.pop()
			if node_depth + 1 < d and node.right is not None:
				stack.append((node.right, node_depth + 1))
				self.traverse_left(stack, node.right, node_depth + 1, d)
			if node_depth == d - 1:
				a = TreeNode(v)
				a.left = node.left
				node.left = a
				b = TreeNode(v)
				b.right = node.right
				node.right = b
		return root


class Solution:

	def addOneRow(self, root, v, d):
		if not root:
			return
		if d == 1:
			new = TreeNode(v)
			new.left = root
			return new
		if d == 2:
			(right, left) = (TreeNode(v), TreeNode(v))
			right.right = root.right
			left.left = root.left
			(root.right, root.left) = (right, left)
		else:
			self.addOneRow(root.right, v, d - 1)
			self.addOneRow(root.left, v, d - 1)
		return root


class Solution:

	def addOneRow(self, root, v, d):
		if d == 1:
			nrt = TreeNode(v)
			nrt.left = root
			return nrt
		level = 1
		que = [root]
		d -= 1
		(beg, end) = (0, 1)
		while beg < end:
			lev_cnt = 0
			i = beg
			if level == d:
				while i < end:
					p = que[i]
					(lt, rt) = (TreeNode(v), TreeNode(v))
					lt.left = p.left
					p.left = lt
					rt.right = p.right
					p.right = rt
					i += 1
				return root
			while i < end:
				p = que[i]
				if p.left:
					que.append(p.left)
					lev_cnt += 1
				if p.right:
					que.append(p.right)
					lev_cnt += 1
				i += 1
			beg = end
			end += lev_cnt
			level += 1
		return root


class Solution:

	def addOneRow(self, root, v, d):
		(q, depth) = ([root], 1)
		while depth != d:
			(parent, q, depth) = (q, [kid for node in q for kid in (node.left, node.right) if kid], depth + 1)
		if d != 1:
			for node in parent:
				(node.left, node.right, node.left.left, node.right.right) = (TreeNode(v), TreeNode(v), node.left, node.right)
			return root
		else:
			(first, first.left) = (TreeNode(v), root)
			return first


class Solution:

	def addOneRow(self, root, v, d):
		(dummy, dummy.left) = (TreeNode(None), root)
		row = [dummy]
		for _ in range(d - 1):
			row = [kid for node in row for kid in (node.left, node.right) if kid]
		for node in row:
			(node.left, node.left.left) = (TreeNode(v), node.left)
			(node.right, node.right.right) = (TreeNode(v), node.right)
		return dummy.left