Given a binary tree, return the *level order* traversal of its nodes' values. (ie, from left to right, level by level).

For example:

Given binary tree `[3,9,20,null,null,15,7]`

,

3 / \ 9 20 / \ 15 7

return its level order traversal as:

[ [3], [9,20], [15,7]]

There are two general strategies to traverse a tree:

*Depth First Search*(`DFS`

)In this strategy, we adopt the

`depth`

as the priority, so that onewould start from a root and reach all the way down to certain leaf,and then back to root to reach another branch.The DFS strategy can further be distinguished as

`preorder`

,`inorder`

, and`postorder`

depending on the relative orderamong the root node, left node and right node.*Breadth First Search*(`BFS`

)We scan through the tree level by level, following the order of height,from top to bottom. The nodes on higher level would be visited beforethe ones with lower levels.

On the following figure the nodes are numerated in the order you visit them,please follow `1-2-3-4-5`

to compare different strategies.

Here the problem is to implement split-level BFS traversal : `[[1], [2, 3], [4, 5]]`

.

**Algorithm**

The simplest way to solve the problem is to use a recursion. Let's first ensure that the tree is not empty, and then call recursively the function `helper(node, level)`

, which takes the current node and its level as the arguments.

This function does the following :

The output list here is called

`levels`

, and hence the current level isjust a length of this list`len(levels)`

.Compare the number of a current level`len(levels)`

with a node level`level`

.If you're still on the previous level - add the new one by adding a new list into`levels`

.Append the node value to the last list in

`levels`

.Process recursively child nodes if they are not

`None`

:`helper(node.left / node.right, level + 1)`

.

**Implementation**

!?!../Documents/102_LIS.json:1000,509!?!

**Complexity Analysis**

Time complexity : since each node is processedexactly once.

Space complexity : to keep the output structure whichcontains

`N`

node values.

**Algorithm**

The recursion above could be rewritten in the iteration form.

Let's keep nodes of each tree level in the *deque* `deq`

structure,which provides both-sides push and pop in time.

The zero level contains only one node `root`

. The algorithm is simple :

Initiate

`deq`

with a`root`

and start from the level number`0`

:`level = 0`

.While

`deq`

is not empty :Start the current level by adding an empty list into output structure

`levels`

.Compute how many elements should be on the current level : it's a

`deq`

length.Pop out all these elements from

`deq`

and add them into the currentlevel.Push their child nodes into the

`deq`

for the next level.Go to the next level

`level++`

.

**Implementation**

**Complexity Analysis**

Time complexity : since each node is processedexactly once.

Space complexity : to keep the output structure whichcontains

`N`

node values.

There are *N* gas stations along a circular route, where the amount of gas at station *i* is `gas[i]`

.

You have a car with an unlimited gas tank and it costs `cost[i]`

of gas to travel from station *i* to its next station (*i*+1). You begin the journey with an empty tank at one of the gas stations.

Return the starting gas station's index if you can travel around the circuit once in the clockwise direction, otherwise return -1.

**Note:**

- If there exists a solution, it is guaranteed to be unique.
- Both input arrays are non-empty and have the same length.
- Each element in the input arrays is a non-negative integer.

**Example 1:**

Input:gas = [1,2,3,4,5]cost = [3,4,5,1,2]Output:3Explanation:Start at station 3 (index 3) and fill up with 4 unit of gas. Your tank = 0 + 4 = 4Travel to station 4. Your tank = 4 - 1 + 5 = 8Travel to station 0. Your tank = 8 - 2 + 1 = 7Travel to station 1. Your tank = 7 - 3 + 2 = 6Travel to station 2. Your tank = 6 - 4 + 3 = 5Travel to station 3. The cost is 5. Your gas is just enough to travel back to station 3.Therefore, return 3 as the starting index.

**Example 2:**

Input:gas = [2,3,4]cost = [3,4,3]Output:-1Explanation:You can't start at station 0 or 1, as there is not enough gas to travel to the next station.Let's start at station 2 and fill up with 4 unit of gas. Your tank = 0 + 4 = 4Travel to station 0. Your tank = 4 - 3 + 2 = 3Travel to station 1. Your tank = 3 - 3 + 3 = 3You cannot travel back to station 2, as it requires 4 unit of gas but you only have 3.Therefore, you can't travel around the circuit once no matter where you start.

**Intuition**

The first idea is to check every single station :

Choose the station as starting point.

Perform the road trip and check how much gas we have in tankat each station.

That means time complexity, and for sure one coulddo better.

Let's notice two things.

It's impossible to perform the road trip if

`sum(gas) < sum(cost)`

. In this situation the answer is`-1`

.

One could compute total amount of gas in the tank `total_tank = sum(gas) - sum(cost)`

during the round trip, and then return `-1`

if `total_tank < 0`

.

It's impossible to start at a station

`i`

if`gas[i] - cost[i] < 0`

,because then there is not enough gas in the tank to travel to`i + 1`

station.

The second fact could be generalized. Let's introduce`curr_tank`

variable to track the current amount of gas in the tank. If at some station `curr_tank`

is lessthan `0`

, that means that one couldn't reach this station.

Next step is to mark this station as a new starting point,and reset `curr_tank`

to zero since one starts with no gas in the tank.

**Algorithm**

Now the algorithm is straightforward :

Initiate

`total_tank`

and`curr_tank`

as zero, andchoose station`0`

as a starting station.Iterate over all stations :

Update

`total_tank`

and`curr_tank`

at each step,by adding`gas[i]`

and subtracting`cost[i]`

.If

`curr_tank < 0`

at`i + 1`

station,make`i + 1`

station a new starting point andreset`curr_tank = 0`

to start with an empty tank.

Return

`-1`

if`total_tank < 0`

and`starting station`

otherwise.

**Why this works**

Let's imagine the situation when `total_tank >= 0`

andthe above algorithm returns as a starting station.

Algorithm directly ensures that it's possible to go from to the station .But what about the last part of the round tripfrom the station to the station ?

How one could ensure that it's possible to loop around to ?

Let's use here the proof by contradictionand assume that there is a station such that one couldn't reach this station starting from .

The condition `total_tank >= 0`

could be written as

where .

Let's split the sum on the right side by the starting station and unreachable station `k`

:

The second term is negative by the algorithm definition - otherwise the starting station would be before .It could be equal to zero only in the case of .

Equations `(2)`

and `(3)`

together results in

At the same time the station is supposed to be unreachablefrom that means

Eqs. `(4)`

and `(5)`

together result in a contradiction. Therefore, the initial assumption — that there is a station such that one couldn't reach this station starting from — must be false.

Hence, one could do a round trip starting from ,that makes to be an answer. The answer is unique according to the problem definition.

**Implementation**

!?!../Documents/134_LIS.json:1000,746!?!

**Complexity Analysis**

Time complexity : since there is onlyone loop over all stations here.

Space complexity : since it's a constant space solution.

**Further reading**

There are numerous variations of gas problem, here are some examples :

Find the cheapest path between two stations if at most Δ stops are allowed.

Find the cheapest path between two stations if the vehicle has a given tank capacity.

Given two binary trees, write a function to check if they are the same or not.

Two binary trees are considered the same if they are structurally identical and the nodes have the same value.

**Example 1:**

Input:1 1 / \ / \ 2 3 2 3 [1,2,3], [1,2,3]Output:true

**Example 2:**

Input:1 1 / \ 2 2 [1,2], [1,null,2]Output:false

**Example 3:**

Input:1 1 / \ / \ 2 1 1 2 [1,2,1], [1,1,2]Output:false

**Intuition**

The simplest strategy here is to use recursion. Check if `p`

and `q`

nodes are not `None`

, and their values are equal.If all checks are OK, do the same for the child nodesrecursively.

**Implementation**

!?!../Documents/100_LIS.json:1000,373!?!

**Complexity Analysis**

Time complexity : , where N is a number of nodes in the tree, since one visitseach node exactly once.

Space complexity : in the best case of completely balanced tree and in the worst caseof completely unbalanced tree, to keep a recursion stack.

**Intuition**

Start from the root and then at each iteration pop the current node out of the deque. Then do the same checks as in the approach 1 :

`p`

and`p`

are not`None`

,`p.val`

is equal to`q.val`

,

and if checks are OK, push the child nodes.

**Implementation**

**Complexity Analysis**

Time complexity : since each node is visitedexactly once.

Space complexity : in the best case of completely balanced tree and in the worst caseof completely unbalanced tree, to keep a deque.

Given two arrays, write a function to compute their intersection.

**Example 1:**

Input:nums1 = [1,2,2,1], nums2 = [2,2]Output:[2]

**Example 2:**

Input:nums1 = [4,9,5], nums2 = [9,4,9,8,4]Output:[9,4]

**Note:**

- Each element in the result must be unique.
- The result can be in any order.

**Intuition**

The naive approach would be to iterate along the first array `nums1`

and to check for each value if this value in `nums2`

or not. If yes - add the value to output. Such an approach would result in a pretty bad time complexity, where `n`

and `m`

are arrays' lengths.

To solve the problem in linear time, let's use the structure

`set`

,which provides`in/contains`

operation in time inaverage case.

The idea is to convert both arrays into sets, and then iterate over the smallest set checking the presence of each element in the larger set.Time complexity of this approach is in the average case.

!?!../Documents/349_LIS.json:1000,352!?!

**Implementation**

**Complexity Analysis**

Time complexity : , where

`n`

and`m`

are arrays' lengths. time is used to convert`nums1`

into set, time is used to convert`nums2`

, and`contains/in`

operations are in the average case.Space complexity : in the worst case whenall elements in the arrays are different.

**Intuition**

There are built-in intersection facilities,which provide time complexity in the average case and time complexity in the worst case.

In Python it's intersection operator, in Java - retainAll() function.

**Implementation**

**Complexity Analysis**

Time complexity : in the average case and in the worst case when load factor is high enough.

Space complexity : in the worst case whenall elements in the arrays are different.

Given a binary tree, count the number of uni-value subtrees.

A Uni-value subtree means all nodes of the subtree have the same value.

**Example :**

Input:root = [5,1,5,5,5,null,5] 5 / \ 1 5 / \ \ 5 5 5Output:4

**Intuition**

Given a node in our tree, we know that it is a univalue subtree if it meets one of the following criteria:

- The node has no children (base case)
- All of the node's children are univalue subtrees, and the node and its children all have the same value

With this in mind we can perform a depth-first-search on our tree, and test if each subtree is uni-value in a bottom-up manner.

!?!../Documents/250_Count_Univalue_SUbtrees.json:1000,518!?!

**Algorithm**

**Complexity Analysis**

Time complexity : .

Due to the algorithm's depth-first nature, the

`is_uni`

status of each node is computed from bottom up. When given the`is_uni`

status of its children, computing the`is_uni`

status of a node occurs inThis gives us time for each node in the tree with total nodes for a time complexity of

Space complexity : , with

`H`

being the height of the tree. Each recursive call of`is_uni`

requires stack space. Since we fully process`is_uni(node.left)`

before calling`is_uni(node.right)`

, the recursive stack is bound by the longest path from the root to a leaf - in other words the height of the tree.

**Algorithm**

We can use the intuition from approach one to further simplify our algorithm. Instead of checking if a node has no children, we treat `null`

values as univalue subtrees that we don't add to the count.

In this manner, if a node has a `null`

child, that child is automatically considered to a valid subtree, which results in the algorithm only checking if other children are invalid.

Finally, the helper function checks if the current node is a valid subtree but returns a boolean indicating if it is a valid component for its parent. This is done by passing in the value of the parent node.

The above code is a commented version of the code here, originally written by Stefan Pochmann.

**Complexity Analysis**

Time complexity : . Same as the previous approach.

Space complexity : , with

`H`

being the height of the tree. Same as the previous approach.

Written by @alwinpeng.

Given a string that contains only digits `0-9`

and a target value, return all possibilities to add **binary** operators (not unary) `+`

, `-`

, or `*`

between the digits so they evaluate to the target value.

**Example 1:**

Input:`"123",`

num=target= 6Output:["1+2+3", "1*2*3"]

**Example 2:**

Input:`"232",`

num=target= 8Output:["2*3+2", "2+3*2"]

**Example 3:**

Input:`"105",`

num=target= 5Output:["1*0+5","10-5"]

**Example 4:**

Input:`"00",`

num=target= 0Output:["0+0", "0-0", "0*0"]

**Example 5:**

Input:`"3456237490",`

num=target= 9191Output:[]

**Intuition**

Let us first look at what the question asks us to do before getting at the approach to solve it. So, we are given a string of numbers and 3 different operators:

`+`

Addition,`-`

Subtraction or`*`

Multiplication

We have to find all possible combinations of binary operators between the digits so that the overall value of the resulting expression becomes equal to a given target value. Let us look at a few possibilities of what it means exactly to *place the operators between digits* so that the question becomes clearer.

Let's say we are given the following set of digits `"123456789"`

and the target value given to us is `45`

. Let us see some of the possible resulting expressions that we can get by placing the operators in different locations.

1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 + 9 = 451 + 2 - 3 + 4 - 5 + 6 - 7 + 8 - 9 = -31 + 2 * 3 - 4 + 5 + 6 - 7 * 8 - 9 = -511 + 2 + 3 + 4 + 5 - 6 * 7 + 8 * 9 = 45

These are just 4 of the many resulting expressions that are possible by using the given string of digits and the three operators.

By looking at the above examples we can't really figure out any specific pattern among the resulting expressions that tells us which of them will give us the resulting target.

Since the question explicitly states that we are given binary operators, this means that each of the operator would require two operands.

We can consider each of our digits as an operand.

This means that between every pair of digits we can have any of the three operators i.e. , or .

If you've looked at the question's statement and the examples that are given in the question, you would realize that there is an example where the digits are `"105"`

and the target value is `5`

. For this particular example, there are two expressions given to us and they are `1*0+5`

and `10-5`

.

The second expression is something that you need to look out for before getting to solve this question because this complicates things a bit.

It would have been an easier question to solve if we just had to consider those expressions that simply had *digits as operands*.

But, in this question, we can have all sorts of digits getting together and forming a bigger number that becomes a part of the expression. Let us look at some example expressions for the digits `"123456"`

and target `30`

.

1 * 23 - 4 + 5 + 6 = 3012 - 3 * 4 + 5 * 6 = 301 - 23 - 4 + 56 = 30

So this means that although the number of operators are defined for us i.e. 3 different binary operators, but the number of operands are **not really well defined for us**.

This is a big portion of the original problem that we need to address in our solution.

Since we are asked to find out all of the valid expressions whose value equals the given target and we don't really know what specific operator between two operands would eventually give us a valid expression,

We try out all of the options.

This means once we have defined what the operands are for our given expression, we would have three possible choices of operators between each consecutive pair of operands.

From an implementation perspective, what would an operand imply with respect to our original string?

An operand would be an integer formed from a substring of our original string.

Let's look at two different array partitions for the given string `"123456789"`

Since we are required to return all of the valid expressions that evaluate to a given target value, we have to try all possible partitions of the given array thereby considering all of the possible operands that can be formed from the digits.

There is a very simple way of incorporating this into our algorithm. Right now, at every point in the algorithm, we have three different choices corresponding to the three different operators.

The way we incorporate these partitions is by considering a 4th operator as well which simply moves one step forward and extends the current operand by one digit. Essentially, going from 12 --> 123 is a NO OP operand in our implementation. (12 * 10) + 3.

Now we have 4 different recursion paths in our algorithm and we have to try out all of them to see which ones lead to a potential solution.

This `try out everything`

hints at a backtracking solution and that is exactly what we are going to look at here.

**Algorithm**

Let's quickly look at the steps involved in our backtracking algorithm before looking at the pseudo-code.

- As discussed above, we have multiple choices of what operators to use and what the operands can be and hence, we have to look at all the possibilities to find
valid expressions.*all* - Our recursive call will have an
`index`

which represents the current digit we're looking at in the original`nums`

string and also the expression string built till now. - At every step, we have exactly 4 different recursive calls. The
`NO OP`

call simply extends the`current_operand`

by the current digit and moves ahead. Rest of the recursive calls correspond to`+`

,`-`

, and`*`

. - We keep on building our expression like this and eventually, the entire
`nums`

string would be processed. At that time we check if the expression we built till now is a valid expression or not and we record it if it is a valid one.

1. procedure recurse(digits, index, expression):2. if we have reached the end of the string:3. if the expression evaluates to the target:4. Valid Expression found!5. else:6. try out operator 'NO OP' and recurse7. try out operator * and recurse8. try out operator + and recurse9. try out operator - and recurse

The algorithm now looks pretty straightforward. However, the implementation is something that needs more thought and there are some things that we need to address before actually looking at the implementation.

When we are done building an expression out of all of the digits in our original string i.e. the base case, then we check if the expression is a valid expression or not. Right ?

How do we actually check if an expression is a valid one or not if all we have is a string representing the expression and not the integer value for the same?

Well, one way to go about this is to write a custom `eval`

function that takes in a string and returns the value of that expression. If you do that (Python people can use the inbuilt function `eval`

for this), you will get a TLE i.e. time limit exceeded error.

**Can't we keep track of the expression's value on the fly?**

Well yes. That's the idea we will go with. Instead of just keeping track of what the expression string is, we will also keep track of it's value along the way so that when the recursion hits the base case, we can check in time if the expression's value equals the target value or not.

The implementation would have been straightforward had it just been `+`

and `-`

operators involved. This is because both these operators have an equal precedence. That means that we can continue to evaluate the expression on the fly without any problems. Have a look at the following example.

So far so good. Now let us add the `*`

operator as well and see how building the expression on the fly like this breaks.

What we mean by building the expression on the fly is that we keep track of the expression's value till now and we simply consider that value as one of the two operands for our operators. As we can see from the two examples above, this would have worked had it just been `+`

and `-`

operators.

But, this approach is bound to fail because the `*`

operator takes precedence over `+`

and `-`

. The `*`

operator would require the ** actual** previous operand in our expression rather than the current value of the expression. i.e. In the above example, the

`*`

operator needed `2`

rather than `12`

to get us the correct value of `18`

.**How to handle this?**

The idea on how to handle this problem springs from the discussion above. We simply need to keep track of the last operand in our expression and how it modified the expression's value overall so that when we consider the `*`

operator, we can **reverse** the effects of the previous operand and consider it for multiplication. Let's take a look at the example that was breaking before.

Now we can look at the actual implementation of this algorithm.

**Complexity Analysis**

Time Complexity:

- At every step along the way, we consider exactly 4 different choices or 4 different recursive paths. The base case is when the value of
`index`

reaches i.e. the length of the`nums`

array. Hence, our complexity would be . - For the base case we use a
`StringBuilder::toString`

operation in Java and`.join()`

operation in Python and that takes time. Here represents the length of our expression. In the worst case, each digit would be an operand and we would have digits and operators. So . This is for one expression. In the worst case, we can have valid expressions. - Overall time complexity = .

- At every step along the way, we consider exactly 4 different choices or 4 different recursive paths. The base case is when the value of
Space Complexity:

- For both Python and Java implementations we have a list data structure that we update on the fly and only for valid expressions do we create a new string and add to our
`answers`

array. So, the space occupied by the intermediate list would be since in the worst case the expression would be built out of all the digits as operands. - Additionally, the space used up by the recursion stack would also be since the size of recursion stack is determined by the value of
`index`

and it goes from all the way to . - We don't consider the space occupied by the
`answers`

array since that is a part of the question's requirement and we can't reduce that in any way

- For both Python and Java implementations we have a list data structure that we update on the fly and only for valid expressions do we create a new string and add to our

**EDIT:**The previous implementation of the algorithm, although correct, lead me to write an incorrect complexity analysis section. I've re-written the algorithm from scratch and corrected the complexity analysis as well. Sorry for the inconvenience to all the readers. The core idea of the algorithm is still the same. That hasn't changed.

Special thanks to @ufarooqi, @vortexwolf for providing correct complexity analysis in the discussion forum leading to corrections in the article. Pardon me if I've missed out on any other names :)

Analysis written by: @sachinmalhotra1993.