#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 (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.

Breadth-first search, Wikipedia

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)
	}
}