Solving Recursion Coding Problems

Solving Recursion Coding Problems with Explanations

Photo on Wikipedia

As tree is a recursive data structure, many tree related problems can be solved recursively, please find these problem from binary tree and binary search tree.

1. Question list

1. Climbing stairs G4G Leetcode Easy
2. Longest univalue path Leetcode Easy Binary Tree
3. Minimum Distance Between BST Nodes Leetcode Easy BST
4. Reverse a linked list using recursion Easy
5. Reverse a string using recursion Techie Easy todo
6. Number of paths G4G Leetcode Medium todo

2. C++ Implementation

Climbing stairs

You are climbing a staircase. It takes n steps to reach the top. Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?

Method 1: Recursion

int climbStairs(int s) 
{ 
    if (n <= 2)//0,1,2,3,5,8
        return n;
    return climbStairs(n-1) + climbStairs(n-2); 
}

Explanation

1. As each time you can either climb 1 or 2 steps, the person can reach the n’th stair from either (n-1)’th stair or from (n-2)’th stair, so we can add up ways of (n-1) and (n-2) to get the result for n stairs.
2. Note that it is slightly different from than Fibonacci numbers shown below. Thus we have to define the base case if n ≤ 2.
3. Time complexity is exponential. T(n) = T(n-1) + T(n-2) + 1 = 2^n = O(2^n), space complexity: O(n). Since climbStairs(n-1) gets evaluated completely before climbStairs(n-2), there will never be more than n levels of recursion.

Fibonacci numbers:
Pattern 1: 0,1,1,2,3,5,8...
Pattern 2: 1,1,2,3,5,8,13...
Our numbers:
0,1,2,3,5,8,13...

Method 2: Dynamic programming-memoization, ref: G4G.

int climbStairs(int n) 
{
    unordered_map<int, int>steps;
    steps[0] = 0;
    steps[1] = 1;
    steps[2] = 2;
    for (int i = 3; i <= n; i++){
        steps[i] = steps[i-1] + steps[i-2];
    }
    return steps[n];
}

Explanation

1. Use Bottom-Up Approach: Suppose we need to solve the problem for N, We start solving the problem with the smallest possible inputs and store it for the future. Now as you calculate for the bigger values use the stored solutions (solution for smaller problems).
2. Time Complexity: O(n) , Space Complexity : O(n)

We can also use Top-Down Approach to solve this problem which still uses recursion but instead of calculating each sub problem, first check if solution is already available, if yes then use it else calculate and store it for future. Ref: https://algorithms.tutorialhorizon.com/introduction-to-dynamic-programming-fibonacci-series/

Method 3: Improved dynamic programming

int climbStairs(int n) 
{
    int result = n; //if n < 3, return n (0, 1, 2)
    int a = 1, b = 2;
    for (int i = 3; i <= n; i++){
        result = a + b;
        a = b;
        b = result;
    }
    return result;
}

Explanation

1. We can optimize the space used in method 2 by storing the previous two numbers only because that is all we need to get the next number in the series.
2. Time Complexity: O(n), Extra Space: O(1).

Longest univalue path

Given a binary tree, find the length of the longest path where each node in the path has the same value. This path may or may not pass through the root.

int postOrder(TreeNode* t, int &result) {
    if(t == NULL) return 0;
    int max_l = postOrder(t->left, result);
    int max_r = postOrder(t->right, result);
    //extend 1 or to be 0. 
    max_l = (t->left && t->left->val == t->val) ? ++max_l:0;
    max_r = (t->right && t->right->val == t->val) ? ++max_r:0;
    
    result = max(result, max_l + max_r); //update the final result
    
    //return to the parent’s parent node
    //only through one side is valid path
    return max(max_l, max_r); 
}
int longestUnivaluePath(TreeNode* root) {
    int result = 0;
    postOrder(root, result);
    return result;
}

Explanation

1. We use a helper to complete as the root node may not be included which means we can’t return the longest path so far for each recursive call. Instead, we need to track the longest path for each step and return only the greater one among left and right paths.
2. The reason we either add 1 to max_l or max_r or set it to be 0 is that: if the value of the root node is different than that of (say left child), the number of edges to the left child will be 0.
3. Time Complexity: O(N), where N is the number of nodes in the tree. We process every node once.
4. Space Complexity: O(H), where H is the height of the tree. Our recursive call stack could be up to H.
5. The reason we can’t return the longest path so far for each recursive call is illustrated below. If we return the longest path so far, we will get the result of 3 instead of the correct answer 2. Because only through one side is a valid path. The correct way to handle it is to update the final result (twice in the figure below).

The moments where I got stuck

I have tried several ways to implement using only one function but ended up in failure. The one pasts the most test cases is shown below. but it fails in the case when the tree looks like above.

int longestUnivaluePath(TreeNode *root){
    if (!root)
        return 0;
    int left = longestUnivaluePath(root->left);
    int right = longestUnivaluePath(root->right);
    int max = left > right ? left: right;
    if (left >= right && root->left && root->val == root->left->val)
        max++;
    if (left <= right && root->right && root->val == root->right->val)
        max++;
    if (left!=right && root->left && root->right && root->val == root->right->val && root->val == root->left->val)
        max++;
    return max;
}

For this kind of question, I concluded that before figuring out a solution, it’s better to understand some test cases and the expected answers. If we first draw several binary trees with different patterns, it may be easier to notice we may need a helper function. Don’t start coding until we have a concrete solution.

Possible test cases

Minimum Distance Between BST Nodes

Given a Binary Search Tree (BST) with the root node root, return the minimum difference between the values of any two different nodes in the tree.

void helper(TreeNode* root, int &res, int &pre){
    if(root == nullptr) return;
    helper(root->left, res, pre);
    if(pre != -1) res = min(res, root->val - pre);
    pre = root->val;
    helper(root->right, res, pre);
}
int minDiffInBST(TreeNode* root) {
    int res = INT_MAX, pre = -1;
    helper(root, res, pre);
    return res;
}

Explanation

          4
        /   \
      2      6
     / \    
    1   3
helper(4, INT_MAX, -1)
  helper(2, INT_MAX, -1)
    helper(1, INT_MAX, -1)
      helper(null, INT_MAX, -1) //1’s left
    pre = 1
      helper(null, INT_MAX, 1) //1’s right
  res = min(INT_MAX, 2-1) = 1
  pre = 2
    helper(3, 1, 2)
      helper(null, 1, 2) //3’s left
    res = min(1, 3-2) = 1
    pre = 3
      helper(null, 1, 3) //3’s right, end of 4’s left tree
res = min(1, 4-3) = 1
pre = 4
  helper(6, 1, 4) //start of 4’s right tree
    helper(null, 1, 4) //6’s left
  pre = 6
    helper(null, 1, 6) //6’s right
  res = min(1, 6-4) = 1 //end of 4’s right

1. We can use in-order traversal to compare the current node’s value and previous value and update the result if we found a smaller one
2. T = O(n): number of nodes = number of recursion call (ignoring the null), M = O(logn): depth of tree

The moments where I got stuck

1. I thought we only need to compare the value of the current node and its children and ignored that we need to compare the value of the current node with the largest node (rightmost children) of its left tree and smallest node (left most children) of its right tree (e.g. 5–4 = 1 below), we can achieve this by inorder traversal.

          5
        /   \
      2      8
     / \    
    0   4

2. Draw the recursion calling process to help analyze the problem.

Reverse a linked list using recursion

ListNode* reverse(ListNode* head) {
    if(head == nullptr || head->next == nullptr) return head;
    ListNode *node = reverse(head->next);
    head->next->next = head;
    head->next = nullptr;
    return node;
}

Explanation: article, video

1. The key is to return the last element as a new head and keep returning this new head in each recursive call, so we will eventually get the new head after all recursive is called.

1->2->3->4->null
reverse(1)
  reverse(2)
    reverse(3)
      reverse(4), 4->next is null, return 4 as head, list: 4
    node=4
    3->next->next = 3 (4->next=3), list: 4->3
    3->next = nullptr, list:4->3->null
    return node (4)
  node=4
  2->next->next = 2(3->next=2), list:4->3->2
  2->next = nullptr, list: 4->3->2->null
  return node (4)
node=4
1->next->next = 1(2->next=1), list: 4->3->2->1
1->next = nullptr, list:4->3->2->1->null
return node (4)

The moments where I got stuck

1. I found difficulties in getting the new head after the last call (i.e reverse(1)) is returned and set the last node’s next to null. The code above can solve this problem.

Reverse a string using recursion

void reverse(string &s, int l, int h){
    if(l < h){
        swap(s[l], s[h]);
        reverse(s, l+1, h-1);
    }
}
reverse(s, 0, s.lenght()-1);

For more recursion questions, see Leetcode, G4G, and Techie Delight