Leetcode solution 257: Binary Tree Paths

Problem Statement 

Given a binary tree, return all root-to-leaf paths.

Note: A leaf is a node with no children.

Example:

Input:

   1
 /   \
2     3
 \
  5

Output: ["1->2->5", "1->3"]

Explanation: All root-to-leaf paths are: 1->2->5, 1->3

Problem link

 

Video Tutorial

You can find the detailed video tutorial here

• Youtube
• B站

Thought Process

Easy problem. Use pre-order traversal from root to leaf and keep the recursion path. The recursion returning condition would be when a node doesn’t have left and right children. Note use a string to keep appending is easier than using a string builder, because we need to pop out and reset the string builder.

Caveat

• Handle the single node situation when no "->". E.g.,  A vs A->B

There is also an iterative implementation of this using one stack, similar to BST iterator using one stack problem. 

Solutions

Pre-order traversal

Time Complexity: O(N), each node is visited once
Space Complexity: O(N), N is the total nodes since that's the string length you need

References

• Leetcode official solution

Leetcode solution 124: Binary Tree Maximum Path Sum

Problem Statement 

Given a non-empty binary tree, find the maximum path sum.

For this problem, a path is defined as any sequence of nodes from some starting node to any node in the tree along the parent-child connections. The path must contain at least one node and does not need to go through the root.

Example 1:

Input: [1,2,3]

       1
      / \
     2   3

Output: 6

Example 2:

Input: [-10,9,20,null,null,15,7]

   -10
   / \
  9  20
    /  \
   15   7

Output: 42

Problem link

 

Video Tutorial

You can find the detailed video tutorial here

• Youtube
• B站

Thought Process

When dealing with binary tree related problem, traversals using recursion is our friend. It seems we can perform a post-order traversal, and keep track of the maximum sums.

If the path cannot go across root, then in each post-order step, we will have the max_sum_of_the_left_path, max_sum_of_the_right_path, the current_node_value, we simply return and record

single_path_max = max(the current_node_value, max(max_sum_of_the_left_path, max_sum_of_the_right_path) + current_node_value)

However, the problem allows a path that goes through the root, therefore, we need to also record a max between left + current node value + right, i.e.,

global_max = max(single_path_max, max_sum_of_the_left_path + current_node_value + max_sum_of_the_right_path)

One caveat is in your recursion, we should still return the single_path_max. The reason we should not return the global_max is in that case, it will not be a single node to single node path.

Solutions

Post-order recursion

Time Complexity: O(N), each node is visited once
Space Complexity:No extra space is needed other than the recursion function stack

References

• Leetcode official solution

Leetcode solution 173: Binary Search Tree Iterator

Problem Statement 

Implement an iterator over a binary search tree (BST). Your iterator will be initialized with the root node of a BST.

Calling next() will return the next smallest number in the BST.

Example:

BSTIterator iterator = new BSTIterator(root);
iterator.next();    // return 3
iterator.next();    // return 7
iterator.hasNext(); // return true
iterator.next();    // return 9
iterator.hasNext(); // return true
iterator.next();    // return 15
iterator.hasNext(); // return true
iterator.next();    // return 20
iterator.hasNext(); // return false

Note:

• next() and hasNext() should run in average O(1) time and uses O(h) memory, where h is the height of the tree.
• You may assume that next() call will always be valid, that is, there will be at least a next smallest number in the BST when next() is called.

Problem link

 

Video Tutorial

You can find the detailed video tutorial here

• Youtube
• B站

Thought Process

 

Brute force dump tree into array method

It’s very similar to BST in order traversal. From that train of thought , we can easily have a brute force solution: perform an in-order traversal, dump that order into an array. Then we can have an pointer point to the array and move the pointer forward every time we call next() method. The time complexity of this brute force way is O(N) in the constructor phase (N is the total number of nodes in the tree). Even though we iterate through the tree 2 times, it’s still O(N), hasNext() and Next() would all be O(1). Space complexity is O(N) as well since we need an extra array to store all the elements in the tree.

Brute force way to dump the tree into an array then iterate over the array
Image credit: https://leetcode.com/articles/binary-search-tree-iterator/

In order traversal using stack  

 

In order to reduce memory from O(N) to O(lgN), aka O(h) where h is the height of the tree, an alternative is return the next() inline while we are performing the recursion. The tricky part is if we still perform the in-order traversal using recursion, there is no easier way to plug in the next() method into the recursion call.

We know we can always use stack to simulate recursion (the push function stack part), and by having a tree node in the stack, it’s also easier to track the predecessor  and successor. The starting position should point to the smallest node in the tree, which is the left most node, we keep going left and pushing the nodes we visited to the stack. Whenever next() is called, we return the top of the stack, and we check if there is any right child of the node, if so, continue push the nodes into the stack until we hit the left most one. hasNext() is simply checking if there is still nodes in the stack. The time complexity of next() would be average O(1) even we have a while loop to keep finding the left most child since on high level, each node is still visited only once. Space complexity is O(lgN) since we at most would put the height of tree worth of elements into the stack.

Initial stage
Image credit: https://leetcode.com/articles/binary-search-tree-iterator/

Find the left most child
Image credit: https://leetcode.com/articles/binary-search-tree-iterator/

Solutions

In order traversal using stack

Note in next() method, we don't need to check if there is still element left in the stack. It is the caller's responsibility to check so. It is described in the Java's Iterator interface NoSuchElementException should be thrown.



Time Complexity: next(), hasNext() O(1) on average even with the while loop, think each node is visited essentially only once
Space Complexity: O(lgN), extra stack is needed capped at tree height

References

• Leetcode official solution

Leetcode solution 772: Basic Calculator III

Problem Statement 

Implement a basic calculator to evaluate a simple expression string.

The expression string may contain open ( and closing parentheses ), the plus + or minus sign -, non-negative integers and empty spaces .

The expression string contains only non-negative integers, +, -, *, / operators , open ( and closing parentheses ) and empty spaces . The integer division should truncate toward zero.

You may assume that the given expression is always valid. All intermediate results will be in the range of [-2147483648, 2147483647].

Some examples:

"1 + 1" = 2
" 6-4 / 2 " = 4
"2*(5+5*2)/3+(6/2+8)" = 21
"(2+6* 3+5- (3*14/7+2)*5)+3"=-12

Note: Do not use the eval built-in library function.

Problem link

 

Video Tutorial

You can find the detailed video tutorial here

• Youtube 
• B站

Thought Process

This is an extension problem to Basic Calculator and Basic Calculator II. The differences are this time it really looks like a real calculator where it can do "+-*/" and with brackets.

It's still the same thought process with exactly the same idea before: having two stacks,  one stack for the operator and the other for the operands, and with exactly the same calculating preferences before: calculate * and / before + and -. When seeing right bracket, continue popping till you see the left bracket.

This works fine assuming all the integers are non-negative, which they are supposed to be based on the problem description, and that's what most of the existing online leetcode solutions did as well.

As of 08/18/2019, this doesn't seem to be the case because leetcode decides to include "non-negative" integer test cases. See below case "-1+4*3/3/3"

An "non-negative" integer case

Since we are practicing interviews, so let's also address the non-negative integer case as well

A few caveats

• (New) Handle negative integer starting case:
  

  "-1 + 2" or "-(2+3)*4"

• (New) Handle negative integer in between expression case:

  "1 - (-7)"

• (New) Calculate whenever you can calculate since division order matters

  15 / 3 / 5 should be 1, but it won't work 3 / 5 = 0,  then 15/0 invalid

• Pay attention to the order when popping out operands and calculate, the order matters. 
• The number might not be just single digit, so need to read the char and convert the numbers

Solutions

Two stacks for non-negative integer solution

Keep two stacks, operator and operands as explained in the above "Thought Process"



Time Complexity: O(N), N is the length of the string
Space Complexity: O(N), extra stack is needed

Two stacks for negative integer solution

Essentially how do address the below two situations given the current code structure

• (New) Handle negative integer starting case. I simply just check if the first char in trimmed string is "-", and push a -1 into operands and "*" into operator. (e.g.,  -(a+b) = -1 * (a+b) and -a = -1 * a)
  

  "-1 + 2" or "-(2+3)*4"

• (New) Handle negative integer in between expression case. This is a bit hacky because a  "-" in the middle of the expression could mean two things: a normal minus sign or a negative sigh denoting negative integer. Luckily "1 - - 2" would not be a valid case which means there should always be a left bracket before the negative sign for negative integer. What I did was using isNegativeNumberFollowingLeftBracket to find those cases and put a -1 and * into the operator and operands respectively
  

  "1 - (-7)"

Time Complexity: O(N), N is the length of the string
Space Complexity: O(N), extra stack is needed

References

• Leetcode discussion on the clean solution (didn't work for non-negative integer case)

Leetcode solution 227: Basic Calculator II

Problem Statement 

Implement a basic calculator to evaluate a simple expression string.

The expression string contains only non-negative integers, +, -, *, / operators and empty spaces . The integer division should truncate toward zero.

Example 1:

Input: "3+2*2"
Output: 7

Example 2:

Input: " 3/2 "
Output: 1

Example 3:

Input: " 3+5 / 2 "
Output: 5

Note:

• You may assume that the given expression is always valid.
• Do not use the eval built-in library function.

Problem link

 

Video Tutorial

You can find the detailed video tutorial here

• Youtube 
• B站

Thought Process

This problem is very similar to Basic Calculator. The difference is there is no parenthesis in this one, but there is * and / . We can use similar thought process by having two stacks,  one stack for the operator and the other for the operands. We just need to pay attention the differentiate the operator's priority. For example, when you currently see a "+" or "-"  and previous operator is "*" or "/", you need to pop up the operator stack and calculate. When you currently see a "*" or "/" and previous operator is "+" or "-", you should just keep pushing operator to stack. Else, they are at the same priority, we just do the normal calculation.


A few caveats

• Notice number overflow. "0- 2147483648". I don't think leetcode has this test case but it is a valid one. We should use Long.
• Pay attention to the order when popping out operands and calculate, the order matters. 
• The number might not be just single digit, so need to read the char and convert the numbers

Solutions

Standard generic way

Keep two stacks, operator and operands as explained in the above "Thought Process"


Time Complexity: O(N), N is the length of the string
Space Complexity: O(N), extra stack is needed

Use one stack with two passes

Another neat and clean way to solve this problem is also similar to the "Use the sign method with one stack" in Basic Calculator. The idea is in the first pass, only calculate "*" and "/" and push the values into the stack, then have a 2nd pass to do the "+" and "-" calculations.

Time Complexity: O(N), N is the length of the string
Space Complexity: O(N), extra stack is needed

References

• Leetcode discussion on the clean solution

Leetcode solution 224: Basic Calculator

Problem Statement 

Implement a basic calculator to evaluate a simple expression string.

The expression string may contain open ( and closing parentheses ), the plus + or minus sign -, non-negative integers and empty spaces .

Example 1:

Input: "1 + 1"
Output: 2

Example 2:

Input: " 2-1 + 2 "
Output: 3

Example 3:

Input: "(1+(4+5+2)-3)+(6+8)"
Output: 23

Note:

• You may assume that the given expression is always valid.
• Do not use the eval built-in library function.

Problem link

 

Video Tutorial

You can find the detailed video tutorial here

• Youtube 
• B站

Thought Process

A generic way for solving those calculating numbers problems is to use stack. More specifically, use two stacks: one stack for the operator and the other for the operands.

A few caveats

• Pay attention to the order when popping out operands and calculate, the order matters. 
• The parenthesis matters, 2 - 1 + 2 = 3, while 2 - (1+2) = -1 = 2 - 1 - 2 if you want to remove the bracket you need to change the sign 
• "1000" is a valid expression without any operators 
• The number might not be just single digit, so need to read the char and convert the numbers

Solutions

Standard generic way

Keep two stacks, operator and operands. When we see left bracket, keep pushing to the stack. We calculate the values as normal within the inner most bracket. When we see right bracket, calculate and pop out the left bracket

Time Complexity: O(N), N is the length of the string
Space Complexity: O(N), extra stack is needed

Use the sign method with one stack

The thought process is very similar to use the stacks, in this method, the clever part is it uses only one stack and also pushed a sign. +1 for "+" and -1 for "-1". Whenever there is a left bracket, you push the existing result and the sign into the stack. Whenever there is a right bracket, you pop up the sign and the value. Pretty neat!

Time Complexity: O(N), N is the length of the string
Space Complexity: O(N), extra stack is needed

References

• Leetcode discussion on the clean solution

Leetcode solution 110: Balanced Binary Tree

Problem Statement 

Given a binary tree, determine if it is height-balanced.

For this problem, a height-balanced binary tree is defined as:

a binary tree in which the depth of the two subtrees of every node never differ by more than 1.

Example 1:

Given the following tree [3,9,20,null,null,15,7]:

    3
   / \
  9  20
    /  \
   15   7

Return true.

Example 2:

Given the following tree [1,2,2,3,3,null,null,4,4]:

       1
      / \
     2   2
    / \
   3   3
  / \
 4   4

Return false.

Problem link

 

Video Tutorial

You can find the detailed video tutorial here

• Youtube 
• B站

Thought Process

As described in the problem, it is intuitive to solve this problem recursively, especially given this is a tree related problem. What we can do is get the height of the left sub tree, compared with the right sub tree, then do the logics to see if it’s balanced or not. If at certain level either the left or right sub tree is not balanced, then entire Tree is not balanced. Classic usage for post order traversal.

Solutions

Post order traversal using recursion

Calculate the height of the left subtree, calculate the height of the right subtree, then compare. If it's already not balanced, return -1 and directly return

Time Complexity: O(N), N is the total tree nodes since it is visited once and only once
Space Complexity: O(1), No extra space is needed

References

• Leetcode discussion