You find yourself perched on the precipitous brink of a black and lurid tarn. You know there are fish down there, you just can’t see them. Arnie the Angler wants you to drop a line down, and measure the pools of fishing swimming at every depth.
It’s pretty dark down there, and there’s no light. Now you understand why Weddell Seals swim under the fish and look back up, with the sky as the background and hunt by silhouette.
To make thing easier, it turns out that the fish have arranged themselves in a binary tree, root up. You first need to see how many fish are swimming at depth 
. Let’s assume depth starts at 1.
Why, it’s a simple recursive search! We dive to level , then record at that level.
package questionDepth
type TreeNode struct {
Val int
Left *TreeNode
Right *TreeNode
}
func questionDepth(root *TreeNode, depth int) []*TreeNode {
var result []*TreeNode
if depth != 0 {
depth--
var traverse func(node *TreeNode, d int)
traverse = func(node *TreeNode, d int) {
if node != nil {
if d > 0 {
traverse(node.Left, d-1)
traverse(node.Right, d-1)
} else {
result = append(result, node)
}
}
}
traverse(root, depth)
}
return result
}
This is a nice way to code it, since it’s all self-contained within the closure.
OK, that seems ok, but how much work are we doing? What is the complexity of the solution, assuming that 
is the number of fish nodes?
What if this method is called frequently?
Complexity: we’re visiting every node up to depth , so this is 
.
Turns out Arnie wants to know about a whole bunch of different depths – how can we generate the results faster?
In addition could be a lot of fish in the sea, so it would be better to cache the results if we’re being asked this question a lot. Let’s hold off thinking about what happens if we catch a fish (delete) or throw one back (insert).
Think Dynamic Programming!
package questionDepth
var depths [][]*TreeNode
func questionDepth(root *TreeNode, depth int) []*TreeNode {
if depth == 0 {
return nil
}
depth--
if depths == nil {
depths = append(depths, []*TreeNode{root})
for d := 0; len(depths[d]) != 0; d++ {
var next []*TreeNode
for _, n := range depths[d] {
if n.Left != nil {
next = append(next, n.Left)
}
if n.Right != nil {
next = append(next, n.Right)
}
}
depths = append(depths, next)
}
}
if depth < len(depths) {
return depths[depth]
}
return nil
}
Now we have a nice cache and efficient cache generation algorithm. How can we handle insert/delete?
There are several options here, depending on what you know and what you don’t. The key is, how do we delete or insert while maintaining our data structures?
Insert should be straightforward, as you will know the depth when you insert a node into the tree, and you can append the node to the array at the correct depth.
Delete could be complicated. You’d either need to lose performance by searching for the node to delete, or make the nodes themselves able to be a doubly-linked list for a quick removal.
Something to think about.
Here’s another question. We’re assuming that we’re looking at a generic sort of binary tree. What if it were a heap?
