The Practice to Become Lazy -- Leave your work to subproblems

                         Leave your work to subproblems 

                                                                    --The idea of recursive approach  

  When I had entry level of data structure class in my freshman year, the most elegant and also somewhat mysterious way to write code is using recursive approach.  I still remember, we compared the iterative and the recursive way to reverse  a LinkedList and I was impressed by we could just use 4 line of code to solve this problem.  

     Well,  To appreciate, then understand what is really happened behind scenes, then able to create some recursive code , Finally, know when to use recursive code to solve problem, are 4 different levels that we may go through when we go deep into this interesting way to solve problems. Here are some practice that you may want to train yourself in order to get more clear picture of how recursive function works.  

     To sum up this idea : Lever your work to small problems -- be "Lazy". 

1. Reverse LinkedList 

   Reverse a singly-linked list.

Examples

• L = null, return null
• L = 1 -> null, return 1 -> null
• L = 1 -> 2 -> 3 -> null, return 3 -> 2 -> 1 -> null

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

It is a very old fashion problem and we could certainly do it use iterative and recursive way. But what I am focus on right now is the pattern of ways that we can solve a problem using recursion. 

Here is a very helpful graph that can illustrate the idea:  

 

Before we reverse the LinkedList, we have Node 1 --> Node 2 .... --> Node n. 

-- For a recursive approach, we only need to take care of one base case, which is how to reverse the very first Node 1 , when we already have Node2 .... Node n already reversed. 

   So what we need to do ? 

   1. Let Node2  point to Node 1 

   2. Let Node1 point to Null 

   3. Return the newHead, which is the Node n. (we do not know which node is node n, but we could leave it to the subproblem. 

 After we figured out those 3 steps we need to do, we, therefore, could come up a elegant recursive code: 

Notice that we do not know which one will be return as newHead, so we leave the work for our subproblem which is the dotted line above. 

2.  Reverse LinkedList in Pairs 

Reverse pairs of elements in a singly-linked list.

Examples

• L = null, after reverse is null
• L = 1 -> null, after reverse is 1 -> null
• L = 1 -> 2 -> null, after reverse is 2 -> 1 -> null
• L = 1 -> 2 -> 3 -> null, after reverse is 2 -> 1 -> 3 -> null

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

Here we have a very little requirement change on original problem, but if you would like to try it in a iterative way, the code will become messy and lots of corner cases need to deal with. Here is a graph that could help us to visualize what we need to accomplish: 

So we only need to reverse Node 1 and Node 2  at current level, by assuming that we already down the job in dotted line box, and we will, again, leave that subproblem to further recursive call. That is the the whole idea of being "Lazy". 

  At current level we just need to : 

    1. Let Node 2 point to Node 1

    2. Let Node 1 point to the subproblem, which is the rest of reversed list 

    3. The newHead will be Node 2 in this case, so we return Node 2 as newHead. 

Just like what we said: 

With base case and return newHead, totally 5 line of code !  Can you believe that ^^ 

3.  How to get a deep copy of graph with possible cycles ?  

There are two ways to do this: 1. BFS copy graph, 2. DFS copy graph. 

The second way DFS is related to this "Lazy" topic, but we will also cover the BFS way also. 

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

Notice: We only actually cloned one node: 

      1. Create this clone of this node 

      2. Put this copy into graph 

      3. Add all its neighbors into neighbors list 

What about other node ? Well we leave it to our recursive call when add other neighbors in this node.

            

4 . Delete From Binary Search Tree 

Delete the target key K in the given binary search tree if the binary search tree contains K. Return the root of the binary search tree.

Find your own way to delete the node from the binary search tree, after deletion the binary search tree's property should be maintained.

Assumptions

• There are no duplicate keys in the binary search tree

The function signature is  :  Public TreeNode delete(TreeNode root, int key ) 

which will represent as the root of the subtree that already complete deleted the node that contains key. 

Notice we had three recursive call when : 

 1. current node.key < key 

 2. current node.key > key 

 3. when node.key  == key 

You may find various code to delete a node in BST, but this way is the most elegant one that I found. 

One more last thing: Notice that if this node have two child, we cloud substitute this node with its min node on right sub-tree or the max node in left sub-tree. In this code we find the min in its right sub-tree to do it. 

Hope you enjoyed ! 

Happy Coding ^^ 

Ye Jiang