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 subtreeshould be the left subtree of the new left subtree root, itsoriginal right subtreeshould 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 valuevas the new root of the whole original tree, and the original tree is the new root’s left subtree.

Example 1:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 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:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 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.

## Solution

This is a insertion only with different rules. Here we need to consider three cases:

- If we arrive at the depth
`d`

we insert two nodes with value`v`

as the left and right node of the current node. - If the current node has a left subtree and a right subtree, then we perform a recursive call on its left subtree and right subtree
- If the current node only has a left subtree(or a right subtree) the we perform a recursive call on it left(right) subtree and leave the other side empty.

1
2
3
4
5
6
7
8
9
10
11

data BTree = Node Int BTree BTree | EmptyTree deriving (Show, Eq, Read)
addRow :: BTree -> Int -> Int -> BTree
addRow (Node i left right) v d | (d - 1) == 1 =
Node i (Node v left EmptyTree) (Node v EmptyTree right)
| left /= EmptyTree && right /= EmptyTree =
Node i (addRow left v (d - 1)) (addRow right v (d-1))
| left /= EmptyTree =
Node i (addRow left v (d - 1)) right
| right /= EmptyTree =
Node i left (addRow right v (d - 1))

## Complexity Analysis

The worst time complexity and space complexity are both \(O(n)\) if we want to insert the value as the deepest row in the tree.

Comments powered by Disqus.