Pressing down & Coming back

                         Recursion in Binary Tree  

When we call getSize on a binary tree object

             We could use recursive method to solve many type of questions, especially when the question  can be boiled down to many little sub-problems. Such as the classic merge sort ,  quick sort, and reverse linked list problems. You could find out that the logic we use to sort a big array using merge sort is the same as the logic we use for a smaller size array. The logic we reverse a long linked list is the same as the logic we reverse a linked list with only 2 nodes .. etc. 
            Therefore, when we ever take a look for the binary tree data structure, it is not a surprise that recursive approach will help us to deal with it in a very handy way. For the most cases, we just need to consider a 3 steps approach for a node, which have parent and 2 child nodes. Then apply this logic to every node in the binary tree using recursion. It is both effective and elegant :-) 

            So here are the 3 steps we need to consider : 

            Step 1 : What a node want from his left and right child node 

            Step 2: After receive this value, what this node do at current level

            Step 3: Then what this node should  return to its parent node 

Note: Step 1 and 3 should be the same thing essentially so we used same red color.

-- 1. Check Balance for Binary Tree

Check if a given binary tree is balanced. A balanced binary tree is one in which the depths of every node’s left and right subtree differ by at most 1.

---------------------------------------------------------------------------------------------------------------

According to the definition of a balanced binary tree we could do a height checking for every node's two child node, which will cost O(n*log(n)). We certainly could do better by following the 3 steps pattern above. 

I will copy paste that 3 steps and see what we want for each step: 

             Step 1 : What a node want from his left and right child node 
                 -- We want the height of left subtree and right subtree 

            Step 2: After receive this value, what this node do at current level
                -- We will compare that two value see are we balance at current level 

            Step 3: Then what this node should  return to its parent node
                -- If we still balance at current level , keep passing its height to parent, otherwise a special value like -1, will indicate a un-balanced condition. 


Then according that 3 steps we come out a O(n) solution: 



Could you match the 3 steps with the code above ?

--2 . Maximum Sum Path from One Leaf Node to Another

Given a binary tree in which each node contains an integer number. Find the maximum possible sum from one leaf node to another leaf node. If there is no such path available, return Integer.MIN_VALUE(Java)/INT_MIN (C++).

Examples

  -15

  /    \

2      11

     /    \

    6     14

The maximum path sum is 6 + 11 + 14 = 31.

------------------------------------------------------------------------------------------------------------

 We will keep using the 3 steps above to see what we need to do: 

            Step 1 : What a node want from his left and right child node 

                -- We want the max path sum from leaf node to its left/right node 

            Step 2: After receive this value, what this node do at current level
                --When we could form a leaf to leaf path at current level, we will see if we could          update the global maximum sum by using ( leftSum + rightSum + current.value ) 

            Step 3: Then what this node should  return to its parent node 
                -- return the max path sum from one left node to this node to its parent 


Here is the 3 steps in code : 

-- 3. Maximum Sum Path from Any Node to Any Node

Given a binary tree in which each node contains an integer number. Find the maximum possible sum from any node to any node (the start node and the end node can be the same). 

Assumptions

• ​The root of the given binary tree is not null

Examples

   -1

  /    \

2      11

     /    \

    6    -14

one example of paths could be -14 -> 11 -> -1 -> 2

another example could be the node 11 itself

The maximum path sum in the above binary tree is 6 + 11 + (-1) + 2 = 18

---------------------------------------------------------------------------------------------------------------

 We certainly could still using that 3 steps to process this problem, but since we just completed question 2 , we could, then , consider the difference between this 2 question. 

  Difference 1. We could update the global maximum sum in any level 

                  2. We could not including the left/right sub-result (cause one node value is still valid ). 

Therefore here is the code : 

I still comment the 3 steps for reference ^^ 

-- 4. Least Common Ancestor in  Binary Tree

Given two nodes in a binary tree, find their lowest common ancestor.

Assumptions

• There is no parent pointer for the nodes in the binary tree
• The given two nodes are guaranteed to be in the binary tree

---------------------------------------------------------------------------------------------------

Compare to previous example, the solution for this problem is not very intuitive at beginning and require some definition knowledge about what is a common ancestor in a binary tree. Here is 2 examples: 

        5

      /   \

     9     12

   /  \      \

  2    3      14

The lowest common ancestor of 2 and 14 is 5

The lowest common ancestor of 2 and 9 is 9 

-------------------------

            Step 1 : What a node want from his left and right child node 
                -- We want to know weather the two target node is under their sub-tree 

            Step 2: After receive this value, what this node do at current level
                -- We will combine 2 and 3 steps together, cause according to the two value we get from child node, we will return different value to parent node accordingly 

            Step 3: Then what this node should  return to its parent node 
                 -- if we see both targets appears under right and left subtree, we return current node to indicate current node is the least common ancestor 
                  else if we did not see anything from two child , we return null to tell parent nothing under this node. 


                  else ( we find one node under this node ) we return this founded node value to its parent to indicate this one node is under this current node. 
              

Code is actually very simple :

Hope you enjoyed this special way to consider a binary tree problem with recursion !  

Happy Coding <> 

Ye Jiang 

Understanding DFS Recursion Tree ( 2 )

                  All Parenthesis 2  &&  Combination of Coins

　　After the first blog about how to understand recursive tree, I think we , at least , already had a little sense  that we need to consider a recursion tree from 1.The height of the tree , 2. the branch factor of the tree. On this blog we will use another 2 question to hammer this process and explore more exciting parts about DFS recursion tree.
　

-- All Parenthesis 2

Get all valid permutations of l pairs of (), m pairs of [] and n pairs of {}.

Assumptions

• l, m, n >= 0

Examples

l = 1, m = 1, n = 0, all the valid permutations are ["()[]", "([])", "[()]", "[]()"]

-----------------------------------------------------------------------------------------------------------------------------

  If you review the All parenthesis 1 in the previous blog post, you may come up quickly with a similarly solution ,which is we may carry out 6 parameters for each part of the 6 parenthesis. Besides, the rule to decide weather we can add certain parenthesis will be the same for the this one. However, It is actually more than what you think it might be :-) 

  If you keep that code above there will be 2 obvious defects. 1. It is not appropriate to carry out 7 or 8 parameters for any method, if we ever come to this situation, we need to come up with other solution around.  2.It has a flaw in its logic. Combination like " ( { ) [ } ] "  will appear in the final result. 

  For fixed those 2 defects, we will use a array of integer to represent all number of parenthesis left and maintain a stack to manage the proper parenthesis combination.  

 Here is a solution code: 

 So what is this recursion tree will look like ? 
1. The target length variable is equal to the height = 2 ( l + m + n)
2. The maximum branch factor will be 6, but the actually tree will never reach this point 
-- > O( 6 ^ (2lmn) ) 

-- Combination of Coins

Given a number of different denominations of coins (e.g., 1 cent, 5 cents, 10 cents, 25 cents), get all the possible ways to pay a target number of cents.

Arguments

• coins - an array of positive integers representing the different denominations of coins, there are no duplicate numbers and the numbers are sorted by descending order, eg. {25, 10, 5, 2, 1}
• target - a non-negative integer representing the target number of cents, eg. 99

Assumptions

• coins is not null and is not empty, all the numbers in coins are positive
• target >= 0
• You have infinite number of coins for each of the denominations, you can pick any number of the coins.

Examples

coins = {2, 1}, target = 4, the return should be

[

  [0, 4],   (4 cents can be conducted by 0 * 2 cents + 4 * 1 cents)

  [1, 2],   (4 cents can be conducted by 1 * 2 cents + 2 * 1 cents)

  [2, 0]    (4 cents can be conducted by 2 * 2 cents + 0 * 1 cents)

]

--------------------------------------------------------------------------------------------------------------------

Let just take target = 99 cent, Coins = { 1 , 5 , 10 , 25 } as a example. How would you approach this problem ?  

 There is 2 approach that may solve this problem, and each of them have a different recursion tree. 

     Plan A:.  The tree height = 99, for each level we will have 4 possible branches, which are take 1 ;  1 , 5 : 1 , 5 , 10 ; and take all of them. ( Note that we could add some code to optimal that once the total number of value we has already exceed than target value, we could then stop. ) 

     Plan B:  The tree height = 4, for each level we will have n possible branches, which depends on # of coins we can take for each value. For example if we consider value 25 cents in first level, we will have 4 branches, which are take 0 , 1 , 2  or 3 number of 25 cents in our final results. ( Same idea for the level of 10 we will have 10 branches and 100 for 1 cents) 

What is your choose ?  As a software engineer, we could analyze and compare this 2 plans in both time and space complexity. 

   Plan A : Time --> O( 4^99 ) , Space --> O(99) 

   Plan B : Time --> O( 99^4 ) , Space --> O( 4 ) 

After compare, it is not hard to find out that plan B is much better then plan A ! 

Here is the solution based on Plan B: 

Here you go , building a recursion tree every time you write DFS code will help you better understand the internal working mechanism of you code and evaluate its performance easily !

Happy Coding < >
Ye Jiang


* Update( 7 / 22 / 2017 ) 
Here is another classic example that I want to add into this topic ! 

-- Binary Tree Sub-Path Sum to Target 

Given a binary tree in which each node contains an integer number. Determine if there exists a path (the path can only be from one node to itself or to any of its descendants), the sum of the numbers on the path is the given target number.

Examples

    5

  /    \

2      11

     /    \

    6     14

  /

 3

If target = 17, There exists a path 11 + 6, the sum of the path is target.

If target = 20, There exists a path 11 + 6 + 3, the sum of the path is target.

If target = 10, There does not exist any paths sum of which is target.

If target = 11, There exists a path only containing the node 11.

-----------------------------------------------------------------------------------------------------------
If we keep a actually path from root to current node and then check every possible subpath at each level we will end up with a O(n^2) solution, but for subpath sum we actually could do better :-)

Remember how to get range sum in constant time ? 

-- We preprocessing the array to populate a prefix sum at each position, then the range sum from i - j is = prefixSum( j ) - prefixSum ( i - 1). 

We could do a similar trick in this problem. 
      1.  Use a set to store all previous prefix sum. 
      2.  Keep a value to record total sum from root to current position 
      3. Then look for a possible sub-path sum by --> Set.contains( totalSum - target ) in O(1) time. 


Here is a solution based on the strategy we come up with :



How is this recursive tree will look like ? ?

It will looks like exactly what the tree data structure itself !  😎
and we will traverse this tree in a pre-order sequence.
So  it is a deep first O(n) solution using call stack to simulate ^^


Hope you enjoyed 💫
Ye Jiang

Understanding DFS Recursion Tree ( 1 )

           All Valid Subsets & Permutation & Parentheses 

                                                                                                   

  There are some questions will require you to list all possible subsets of certain characters, or all permutations of some random number. It seems very hard to deal with it when the characters or numbers are in a large scale. For example if let you find all subsets of "ABC", the answer set will only contain 2^3 = 8 elements. However if it become "ABCDEFGHIG" , then we will have 2^10 = 1024 elements in our result set, which is almost impossible to do it manually. That is why this kind of question become very interesting. As a software engineer, we need be able to let computer to do this tedious work for us and it will do it quick & without any mistake. Besides, more importantly, after we write some recursive code, we need to understand how the recursive tree will look like. It is , indeed, a part of the charming of programming. 

-- All Subsets 1 

Given a set of characters represented by a String, return a list containing all subsets of the characters.

Assumptions

• There are no duplicate characters in the original set.

​Examples

• Set = "abc", all the subsets are [“”, “a”, “ab”, “abc”, “ac”, “b”, “bc”, “c”]
• Set = "", all the subsets are [""]
• Set = null, all the subsets are []

---------------------------------------------------------------------------------------------------------------------

We could use backtrack algorithm( we actually discussed this algorithm before ) to solve this easily. 

Here is a solution in JAVA: 

Note, if this backing code is somewhat mysterious to you, then you may want to use pen and paper to draw some call stacks of a simple example like "abc", which will help you to understand what is going on under the hood. ( Here some call stacks I traced ) 

1. Base case determines recursive tree's height 

2. # of times it call itself  in the method body determines the branch factor 

-- All Subsets 2 

How about a almost identical problem with possible duplication of letters ?
 Given a set of characters represented by a String, return a list containing all subsets of the characters.

Assumptions

• There could be duplicate characters in the original set.

​Examples

• Set = "abc", all the subsets are ["", "a", "ab", "abc", "ac", "b", "bc", "c"]
• Set = "abb", all the subsets are ["", "a", "ab", "abb", "b", "bb"]
• Set = "", all the subsets are [""]
• Set = null, all the subsets are []

------------------------------------------------------------------------------------------------------------------------

Well since it is almost identical to the subsets 1, except it may contains some duplicate letters, so only thing we need to add into the solution of the first one is de-duplication steps. 

We added line 9 --> Let same character be in adjacent positions
                 line 22 --> After add this character into final solution we skip all the possible duplications

-- All Permutation 1

Given a string with no duplicate characters, return a list with all permutations of the characters.

Examples

• Set = “abc”, all permutations are [“abc”, “acb”, “bac”, “bca”, “cab”, “cba”]
• Set = "", all permutations are [""]
• Set = null, all permutations are []

-----------------------------------------------------------------------------------------------------------------

Do you feel that all permutation problem is somewhat related to the all subsets problem ? 

Actually are related and we will use the same approach trying to solve it, but remember for all subsets problem we have 2^N cases, which means for any random letter we either add into final solution, or not. 

However, for all permutation problem we will have N * (N-1) * (N-2)* ... *1 = N! cases. 

Here is a working solution in JAVA: 

Notes: the for loop from 17 - 20 was full of mysterious to me at the beginning 

What it will do is start from a position and swap every upcoming position with this one. 

Here are some call stacks. 

--All Permutation 2

So what we gonna do when there are some duplicate letters  -_-   ?

Again we need to de-duplication and the way we do is to keep a set for every branch, and do not swap with a upcoming letter if we already meat it before ( swap two same letter will make no difference in the result ). 



Line 16 and 18 will do the de-duplication job.

-- All Parentheses 1

Given N pairs of parentheses “()”, return a list with all the valid permutations.

Assumptions

• N >= 0

Examples

• N = 1, all valid permutations are ["()"]
• N = 3, all valid permutations are ["((()))", "(()())", "(())()", "()(())", "()()()"]
• N = 0, all valid permutations are [""]

-------------------------------------------------------------------------------------------------

You actually can consider this question as follows: suppose you have k parentheses to use, which means the string length will be 2k ( k left paren + k right paren ). Then suppose you have a 2k length char array, for every position you may have 2 choose : either put '('  or ')'. But wait a second, do we really have 2 choose for every position ?  Definitely not, for example the very first position can not put a ')'. So that is a important point  that this question need to consider.



As you can see from the comment, when considering what to add at current position(index) 
there are 2 possible cases
1. if we still have left paren left, then we could add left paren 
2. if left paren is used more then right paren then we could add right paren at this position. 

if we consider how this recursive tree will look like , First, we will have a 6 level tree ( height is determined by the base case), and for each level, if not considering cutting any branch out, will have 2 branches. Therefore, Time complexity  --> O(2^6) , Space Complexity --> O(6) 


There will be another blog concerning the understanding the recursive tree coming, I hope we all enjoy it.

Happy Coding :-)
Ye Jiang