# README
#+title: 632. Add One Row to Tree #+author: Sebastian N #+auto_tangle: t
** Choosing between BFS and DFS For a binary tree, the worst-case complexity of BFS and DFS is the same.
For BFS, the worst-case scenario is a balanced tree, which requires iteration to hold two rows in memory (current and previous) at the same time. The last row of such a tree contains half of the total number of nodes, so BFS will need $\mathcal{O}(n)$ space.
For DFS, the worst-case scenario is an unbalanced tree consisting of a string of nodes from root to leaf. Each time the function is recursively called, a new stack frame is allocated, which contains more than just the TreeNode. Please see [[https://github.com/golang/go/blob/ddc7d2a80cdac50cbbfb9108b443142f44a5ef1d/src/runtime/stack.go#L530][src/runtime/stack.go]].
I prefer BFS for this problem, because it is inherently about managing rows of the tree. The choice of algorithm is not only about its time and space complexity, but also about the message you are trying to convey.
** BFS Iterate over the tree, row-by-row. Once depth is 2, insert the row below the current one.
Time: $\mathcal{O}(n)$
Space: $\mathcal{O}(n/2) = \mathcal{O}(n)$
#+begin_src go :tangle bfs.go package p0623addonerowtotree
type TreeNode struct { Val int Left *TreeNode Right *TreeNode }
func addOneRow(root *TreeNode, val int, depth int) *TreeNode { #+end_src
Create a dummy node and list of nodes for the current and next rows. The dummy is often called a /sentinel/ value because it's used to deal with edge cases that would otherwise require conditional logic. For this problem, it handles the case where depth is 1 and the root node must be replaced. #+begin_src go :tangle bfs.go dummy := &TreeNode{Left: root} curr := []*TreeNode{dummy} next := []*TreeNode{}
#+end_src
Iterate over nodes until curr contains the parent of the row to be inserted.
Note! A very common mistake that people make here is to allocate a new slice on
each iteration. By swapping curr and next and re-slicing, we can re-use
memory that would otherwise be lost (for the GC to collect). If you do this,
then memory use is $O\left(N\right)$ rather than $O\left(W\right)$.
#+begin_src go :tangle bfs.go
for i := 2; i < depth; i++ {
next = next[:0]
for _, node := range curr {
if node.Left != nil {
next = append(next, node.Left)
}
if node.Right != nil {
next = append(next, node.Right)
}
}
curr, next = next, curr
}
#+end_src
Insert the new row and return. #+begin_src go :tangle bfs.go for _, node := range curr { node.Left = &TreeNode{Val: val, Left: node.Left} node.Right = &TreeNode{Val: val, Left: node.Right} }
return dummy.Left
} #+end_src
** DFS With depth-first search, the tree is traversed while decrementing depth until depth is 2. Then, the current node's children with the new row.
Time: $\mathcal{O}(n)$
Space: $\mathcal{O}(n)$
#+begin_src go :tangle dfs.go package p0623addonerowtotree
type TreeNode struct { Val int Left *TreeNode Right *TreeNode }
func addOneRow(root *TreeNode, val int, depth int) *TreeNode { #+end_src
Special case: replacing the root of the tree. It does not matter whether we set the Left or Right child. #+begin_src go :tangle dfs.go if depth == 1 { return &TreeNode{Val: val, Left: root} } #+end_src
Insert the new row once the depth is 2. Otherwise, traverse further down the tree. #+begin_src go :tangle dfs.go if root == nil { return nil } if depth == 2 { root.Left = &TreeNode{Val: val, Left: root.Left} root.Right = &TreeNode{Val: val, Right: root.Right} } else { root.Left = addOneRow(root.Left, val, depth-1) root.Right = addOneRow(root.Right, val, depth-1) } return root } #+end_src