Teaching to learn: Cousins in Binary Tree

Leetcode: Cousins in Binary Tree

This post is part of series where I will be breaking down coding problems that I have solved and sharing the lessons I learned while finding an answer. The coding language will be in JavaScript.

I don’t know about you but I grew up with a ton of cousins. People are often shocked when they find out I am related to about half the population of my home town (exaggeration.. but really.. it’s ridiculous). Anyway, let’s get at the problem.

Understanding the problem

“Two nodes of a binary tree are cousins if they have the same depth, but have different parents.”

This sums up the majority of what we are doing here. We are given a root node for the binary tree, then an x target and a y target.

The first level (or depth) of this binary tree is considered level 0. This fits the usual motif for us programmers.

We are expected to return a boolean value. Are x and y cousins or not?

x and y are only considered cousins if they have different parents and the same level (a.k.a. depth).

Notes:

The number of nodes in the tree will be between 2 and 100.

Each node has a unique integer value from 1 to 100.

My first thoughts:

This can be done with recursion. It’s a tree structure. When I hear tree or graph, recursion comes to mind.

So yea, recursion. But how do we use it? For this challenge we are searching for two unique values. Searching in a binary tree…. hmmm.

Breadth First Search and Depth First Search.

Ah yes. The two algorithms often used when dealing with trees or graphs. Which one should we use?

In general, bread first search (BFS) is used to find the shortest path to a value. Depth first search (DFS) is typically used when you don’t know where a value is in the tree and you don’t care how far it is to get there.

Since we do not care about the length of the path and we have no idea where these values might be in the tree, let us go with DFS.

Pseudo-code:

1. Define a DFS function inside of our isCousins() function which takes 3 arguments: node, target, level. Level will be defaulted to 0
2. Inside of the DFS function set our first base case. If node is null, return
3. Set our second base case. If node === target and level === 0, return
4. Set our 2 success cases: (1) If node.left exists and it is the target, return an array containing the current node (parent) and current level + 1 (since the target value is a child of the current node). (2) If node.right exists and it is the target, return an array containing the current node (parent) and current level + 1 (since the target value is a child of the current node)
5. Set a left variable which calls our DFS function with node.left and target as arguments
6. Set a right variable which calls our DFS function with node.right and target as arguments
7. If left is truthy (it has a value other than null, 0, or undefined) return left
8. If right is truthy (it has a value other than null, 0, or undefined) return right
9. Outside of our DFS function: We need to call our DFS function. Once for the x argument and once for the y argument (to see if they exist within our binary tree)
10. Set an xParams variable equal to dfs(root, x)
11. Set a yParams variable equal to dfs(root, y)
12. If either xParams or yParams is not truthy, return false
13. If xParams[0] (the parent) and yParams[0] (the parent) are different and xParams[1] (the level) and yParams[1] (the level) are the same, return true
14. Default to return false

The code:

O(n) time / O(1) space

A somewhat lengthy function but we did have a lot of factors to consider here. In our worst scenario we have to check every node in the binary tree to find our values and we end up not finding them at all. This means our worst case time complexity would be O(n). Our space complexity is constant O(1) since we are not creating any data structures dependent on the length of our inputs.

This is a pretty great solution. It does the job in an acceptable time frame. I am not aware of any other way to solve this with a faster time complexity. The worst case would always be O(n) because you would have to search the entire tree to know if the value you are searching for is really there or not.

However we can write this solution differently. Instead of using recursion we can use an iterative approach to do the same thing.

Another solution:

In order to use depth first search iteratively, we can depend on a stack. The stack will allow us to keep track of the nodes we haven’t visited yet as we are moving through our binary tree.

This time I will also use a Map to store the results of our search. There really isn’t any advantage to this over the array that we used in the recursive solution, it is just another way of storing data and retrieving it.

Pseudo-code:

1. Initialize an empty Map to store the results of the search: let results = new Map()
2. Initialize a level variable to store current level: let level = 0
3. Initialize a stack array with a default value of an array containing the root at index 0, and the level at index 1: let stack = [[root, level]]
4. Check if root.val is equal to x or y, if it is: return false (since only 1 node can exist on level 0, there can be no cousins on level 0)
5. Loop while stack.length is > 0. Inside the while loop:
6. Initialize a variable to store the popped data from stack: let data = stack.pop()
7. Initialize a variable to hold the current node from data: let current = data[0]
8. Set level to the current level from data: level = data[1]
9. If current.left exists: if current.left.val is equal to x or y, set current.left.val in the results map with a value of an object which has two properties => parent: current.val, level: level + 1. Push an array containing current.left and level + 1 to the stack
10. If current.right exists: if current.right.val is equal to x or y, set current.right.val in the results map with a value of an object which has two properties => parent: current.val, level: level + 1. Push an array containing current.right and level + 1 to the stack
11. Outside of the while loop: If results.get(x).parent !== results.get(y).parent and results.get(x).level === results.get(y).level: return true
12. Default to return false

The code:

O(n) Time Complexity / O(1) Space Complexity

As you can see we have to keep track of more variables with this solution. Both solutions are kind of difficult to wrap your head around but once you code it out and mess with the gears a little it becomes clear what is going on inside these approaches.

One thing I want to point out about the iterative approach is that the level variable might be a bit confusing to understand at first. The level of our targets (x and y) is always going to be one more than our current node since we are checking for the targets from the parent node, before we actually get to the target nodes themselves.

This means we always need to increment the level by 1 when returning it as a result or pushing it to the stack. This insures we are always getting the correct level for our results.

If you have any other approaches for solving this challenge or any pointers for me, let me know!