Search

Question 1

Minimum Depth of Binary Tree (BFS) (Easy)

Given a binary tree, find its minimum depth.

The minimum depth is the number of nodes along the shortest path from the root node down to the nearest leaf node.

Note: A leaf is a node with no children.

What is the structure most conducive to BFS?

What do we need to keep track of?

Answer 1

The structure we’re looking for is a queue.

We need to keep track of the nodes that we’ve visited by adding and popping things to the queue.

Use an inner and outer while loop to only loop through the nodes of the current depth, removing nodes and adding their children to the end of the queue.

Make sure to check if currentNodes exist before adding them.

Question 2

Symmetrical Tree (BFS OR RECURSION) (Easy)

Answer 2

For each level of the tree, we want to check the symmetry by having pointers from each end and comparing their values. If any nodes are false

Add another level of the tree by setting the current length of the array, and while that value is > 0, shift the old values and add their left and right values to the array. You should only be left with new values for the new iteration.

Hint: Dealing with null values is tough here, so in the solution we map through the array on each iteration, adding either the value or null.

Question 3

Path Sum (Easy)

Given the root of a binary tree and an integer targetSum, return true if the tree has a root-to-leaf path such that adding up all the values along the path equals targetSum.

A leaf is a node with no children.

Answer 3

Set a global variable hasPath that we can set to true if sum is found.

Rather than counting up, count down from targetSum and see if anything hits 0.

Use a recursive inner function that at each level checks if we’re at a leaf (both node.left and node.right are null). If we are, then check if sum === node.val (the remaining value left).

If not, call dfs on both left and right, passing in the node value minus the previous sum.

Question 4

Binary Search (Easy)

Given an array of integers nums which is sorted in ascending order, and an integer target, write a function to search target in nums. If target exists, then return its index. Otherwise, return -1.

You must write an algorithm with O(log n) runtime complexity.

Answer 4

Define search boundries with hi and low.

While low < hi, calculate the midpoint. If midpoint is higher than target, adjust hi to the midpoint - 1, otherwise adjust lo to midpoint.

return nums[pivot] === target ? pivot : -1