Day 2

Photo by Chris Barbalis on Unsplash

## The Problem

Two nodes in a binary tree can be called cousins if they are on the same level of the tree but have different parents. For example, in the following diagram

`4`

and`6`

are cousins.

```
1
/ \
2 3
/ \ \
4 5 6
```

Given a binary tree and a particular node, find all cousins of that node.

https://dailycodingproblem.com

## My Solution

First, I created a Node class in order to construct the binary tree

```
class Node {
constructor (value) {
this.right = null
this.left = null
this.value = value
}
setRight (rightNode) {
this.right = rightNode
return this
}
setLeft (leftNode) {
this.left = leftNode
return this
}
}
```

Next, I defined the tree

```
const tree = new Node(1)
.setLeft(new Node(2)
.setLeft(new Node(4)))
.setRight(new Node(5))
.setRight(new Node(3)
.setRight(new Node(6)))
```

To me, the most applicable search for this problem seemed to be a breadth-first search.

Breadth-first search, Wikipedia

Breadth-first search(BFS) is an algorithm [that] explores all of the neighbor nodes at the present depth prior to moving on to the nodes at the next depth level.

With breadth-first search, it is much easier to get nodes at the same level, since the tree is traversed row after row instead of going down an entire branch and then continuing onto the next branch.

With this in mind, I came up with my first attempt at an algorithm:

```
const findCousins = (tree, number) => {
return recursiveFindCousins([tree], number, 1, 1, [])
}
const recursiveFindCousins = (queue, number, depth, remaining, visited) => {
const node = queue[0]
if (remaining === 0) {
// Increase the depth, clear the visited list, and reset the remaining nodes
return recursiveFindCousins(queue, number, depth + 1, queue.length, [])
} else if (node.value === number) {
// Only return if the depth is greater than 2, otherwise throw an error
if (depth > 2) {
return visited.concat(queue.slice(0, remaining)) // return the cousins
}
return new Error('The number cannot be in the first two rows')
} else {
// --- Prepare for next recursive call ---
queue = queue.concat([node.left, node.right].filter(notNull => notNull))
visited.push(node)
// --- Recursive call ---
return recursiveFindCousins(queue.slice(1), number, depth, remaining - 1, visited)
}
}
```

### Explanation

The `findCousins`

function takes in a tree and a number to look for throughout the tree. It then calls a `recursiveFindCousins`

function with the necessary arguments of a `queue`

, `number`

, `depth`

, `remaining`

, and `visited`

.

The `queue`

argument is the number of remaining nodes in the current queue; this is how the breadth-first logic comes in.

The `number`

argument is the number to look for throughout the tree. This value stays constant throughout all of the recursive calls.

The `depth`

argument is the current depth in the tree. This value is important because if the depth is less than 2, the function should return an error. How can a node have a cousin if there is only a parent with children?

The `remaining`

argument is the number of remaining nodes at the current depth. When remaining reaches 0, the number of remaining nodes is set to the length of the queue, the visited list of nodes (as described below) is cleared, and the depth is incremented.

The `visited`

argument is a list of the nodes that are visited. This list is cleared as soon as the number of remaining nodes hits 0.

### The code was not done, however

In order for the problem to be completed, the values returned could not return the current node nor sibling nodes, only cousin nodes.

To fix this, the array was trimmed accordingly.

See the final code below:

```
const recursiveFindCousins = (queue, number, depth, remaining, visited) => {
const node = queue[0]
if (remaining === 0) {
// Increase the depth, clear the visited list, and reset the remaining nodes
return recursiveFindCousins(queue, number, depth + 1, queue.length, [])
} else if (node.value === number) {
// Only return if the depth is greater than 2, otherwise throw an error
if (depth > 2) {
// Only return every other branch except for the current parent's children
const cousins = visited.concat(queue.slice(0, remaining))
const position = cousins.length - remaining
const pair = Math.floor(position / 2)
const beforePair = cousins.slice(0, 2 * pair)
const afterPair = cousins.slice(2 * (pair + 1))
return beforePair.concat(afterPair)
}
return new Error('The number cannot be in the first two rows')
} else {
// --- Prepare for next recursive call ---
queue = queue.concat([node.left, node.right].filter(notNull => notNull))
visited.push(node)
// --- Recursive call ---
return recursiveFindCousins(queue.slice(1), number, depth, remaining - 1, visited)
}
}
```