Software Developer

Algorithm :
1) Create a stack to store operands (or values). 
2) Scan the given expression and do the following for every scanned element. 
…..a) If the element is a number, push it into the stack 
…..b) If the element is an operator, pop operands for the operator from the stack. Evaluate the operator and push the result back to the stack 
3) When the expression is ended, the number in the stack is the final answer

The idea is to traverse all the leaves and connect them by changing their left and right pointers. We also need to remove them from the Binary Tree by changing left or right pointers in parent nodes. 
One way to solve this is to add the leaves at the beginning of the current linked list and update the head of the list using the pointer to head pointer. Since we insert at the beginning, we need to process leaves in reverse order. For reverse order, we first traverse the right subtree, then the left subtree. We use return values to update left or right pointers in parent nodes.

We have a matrix with n rows and m columns, where each cell, matrix[A][B], denotes whether it is accessible or not.
We will use recursion to solve this problem. We know that the number of ways to reach a cell is the sum of the number of ways to reach the cell to its left and the number of ways to reach the cell above it. Therefore:
No. of ways to reach matrix[i][j] = No. of ways to reach matrix[i-1][j] + No. of ways to reach matrix[i][j-1]
This is because we can only go right or downward from any cell.
Now, we start from a cell and perform recursion to find the number of ways to reach cell (n-1, m-1): 
recur(matrix, n-1, m-1) = recur(matrix, n-2, m-1) + recur(matrix, n-1, m-2)
For each cell, we will check if it is accessible or not. If it is not, we simply return 0, as there is no way to reach it. The base condition would be that if cell (0,0) is accessible, then the number of ways to reach it is 1.
Time Complexity: O(2^(rows+columns))
Auxiliary Space Used: O(rows+columns)

The above solution (recursive) was exponential. We are visiting multiple states over and over, and then recursing for them, which we can surely avoid. To avoid revisiting states that have already been visited, we can store them in a dp array, so that they can be accessed as and when needed. This approach is known as Dynamic Programming.
We know that for any cell (i, j), the number of paths to reach it would be the number of paths to reach cell (i-1, j) + the number of paths to reach cell (i, j-1).
For any accessible cell matrix[i][j], we maintain the count of number of paths to reach this cell in a separate two-dimensional array dp[i][j], where dp[i][j] = dp[i-1][j] + dp[i][j-1], given that cell (i, j) is accessible.
We return the value of dp[i][j] as the answer.
Time Complexity: O(n*m), considering the number of rows is n and columns is m.
Space Complexity: O(n*m), considering the number of rows is n and columns is m.

The question can be approached using recursion. The person can reach nth stair from either (n-1)th stair or from (n-2)th stair. Hence, for each stair n, find out the number of ways to reach n-1th stair and n-2th stair and add them to give the answer for the nth stair. Therefore the expression for such an approach comes out to be : ways(n) = ways(n-1) + ways(n-2)

This is an expression for Fibonacci numbers only, where ways(n) is equal to Fibonacci(n+1). 
Time Complexity: O(2^n) 
The above solution can be optimised using dynamic programming. Maintain an array dp[] and fill it in bottom up manner using the relation :
Dp[i] = dp[i-1] + dp[i-2] for i>=2 
Time complexity: O(N)
Auxiliary Space: O(N)