Day 9 of 30 days of Data Structures and Algorithms and System Design Simplified — Recursion
Welcome back peeps. Hope all’s well. In this post we will cover Recursion as follows —
What and Why Recursion(in 2–3 sentences)?
How does Recursion work?
Important Patterns and Techniques in Recursion Questions
Most Important Questions with Solutions
Tips and Techniques to solve Recursion Questions Fast.
Projects Videos —
All the projects, data structures, SQL, algorithms, system design, Data Science and ML , Data Analytics, Data Engineering, , Implemented Data Science and ML projects, Implemented Data Engineering Projects, Implemented Deep Learning Projects, Implemented Machine Learning Ops Projects, Implemented Time Series Analysis and Forecasting Projects, Implemented Applied Machine Learning Projects, Implemented Tensorflow and Keras Projects, Implemented PyTorch Projects, Implemented Scikit Learn Projects, Implemented Big Data Projects, Implemented Cloud Machine Learning Projects, Implemented Neural Networks Projects, Implemented OpenCV Projects,Complete ML Research Papers Summarized, Implemented Data Analytics projects, Implemented Data Visualization Projects, Implemented Data Mining Projects, Implemented Natural Leaning Processing Projects, MLOps and Deep Learning, Applied Machine Learning with Projects Series, PyTorch with Projects Series, Tensorflow and Keras with Projects Series, Scikit Learn Series with Projects, Time Series Analysis and Forecasting with Projects Series, ML System Design Case Studies Series videos will be published on our youtube channel ( just launched).
Subscribe today!
System Design Case Studies — In Depth
Design Instagram
Design Messenger App
Design Twitter
Design URL Shortener
Design Dropbox
Design Youtube
Design API Rate Limiter
Design Web Crawler
Design Facebook’s Newsfeed
Design Yelp
Design Uber
Design Tinder
Design Tiktok
Design Whatsapp
Most Popular System Design Questions
Mega Compilation : Solved System Design Case studies
Recursion
Importance : Very High
Note : New Recursion with solutions will be added everyday. So keep checking this post daily.
Let’s dive in!
What is Recursion?
Recursion is a technique in which the program/function calls itself.
It has many advantages over the iterative solutions, for e.g its easier to read and write ( and visualize) and minimize the length of the code.
Examples of Recursion problems —
Max depth of a tree
Diameter of a tree
Invert a tree
Flip a tree
Inorder/Preorder/Postorder Tree Traversals
Depth first search in Graphs
Factorial of a number
Tower of Hanoi etc
How does Recursion work?
Recursion is a programming technique where a function calls itself in order to solve a problem. It is used when a problem can be broken down into smaller, identical subproblems.
In recursion, a base case is defined to stop the recursive function calls and prevent infinite looping. The function then calls itself with a modified set of inputs, typically by reducing the size of the problem, until the base case is reached and the function can return a result.
The main gist is — when recursing, the machine remembers previous state of the problem and the information is held in the activation stack.
All the functions that are made recursive have —
- Base Case ( Termination condition)
- Recursive Call (function calls itself)
def func_name():
Recursive call to function func()
func_name()Recursion terminates when it meets/satisfies the base case. It uses extra space in the stack memory.
Important Patterns and Techniques in Recursion Questions
Important patterns and techniques in recursion questions include identifying the base case, understanding how the function calls itself with modified inputs, and recognizing when recursion is an appropriate solution to the problem.
Recursion function solves a problem by calling a copy of itself and dividing and solving smaller subproblems of the original problem recursively .
Patterns → Questions like below belong to Recursion ( not limited to):
Inorder/Preorder/Postorder Tree Traversals
Depth first search in Graphs
Factorial of a number
Tower of Hanoi etc
Most Important Questions with Solutions
Note : New Recursion questions with solutions are added every day. So keep checking this post daily.
Golden rule is — Learn by doing/implementing
In this we will see most important Recursion questions.
Invert Binary Tree
Question —
Given the root of a binary tree, invert the tree, and return its root.
Example :
Input: root = [4,2,7,1,3,6,9]
Output: [4,7,2,9,6,3,1]Solution :
Main Logic/Idea —
The main logic — to invert left tree ( by calling invertTree function recursively) on the left tree. Invert right tree( by calling invertTree function recursively) on the right tree. Assign the right to left and vice versa.
Implementation —
def invertTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
if not root:
return None
temp = root.left
root.left = root.right
root.right = temp
self.invertTree(root.left)
self.invertTree(root.right)
return rootQuestion Link
Similar Pattern —
Reverse Odd Levels of Binary Tree
Full Code Video Explanation ( In progress. Subscribe today for updates) :
— — — — — — — — — — — — — — — — — — — — — — — — — — — — — — —
Flip Equivalent Binary Trees
Question —
For a binary tree T, we can define a flip operation as follows: choose any node, and swap the left and right child subtrees.
A binary tree X is flip equivalent to a binary tree Y if and only if we can make X equal to Y after some number of flip operations.
Given the roots of two binary trees root1 and root2, return true if the two trees are flip equivalent or false otherwise.
Example :
Input: root1 = [1,2,3,4,5,6,null,null,null,7,8], root2 = [1,3,2,null,6,4,5,null,null,null,null,8,7]
Output: trueSolution :
Main Logic/Idea —
The main gist is — Flip the left and right subtree, flip the roots ( right and left) recursively. If the trees node/root value is not equal then return False.
Implementation —
def flipEquiv(self, root1: Optional[TreeNode], root2: Optional[TreeNode]) -> bool:
if not root1 or not root2:
return not root1 and not root2
if root1.val != root2.val:
return False
ans = (self.flipEquiv(root1.left,root2.left) and self.flipEquiv(root1.right,root2.right)) or (self.flipEquiv(root1.left,root2.right) and self.flipEquiv(root1.right,root2.left))
return ansQuestion Link
Similar Pattern —
Smallest String Starting From Leaf
Delete Leaves With a Given Value
Full Code Video Explanation ( In progress. Subscribe today for updates) :
— — — — — — — — — — — — — — — — — — — — — — — — — — — — — — —
Binary Tree Inorder Traversal
Question —
Given the root of a binary tree, return the inorder traversal of its nodes' values.
Example:
Input: root = [1,null,2,3]
Output: [1,3,2]Solution :
Main Logic/Idea —
The main logic is to follow Inorder traversal rule — Left, Root, Right.
So first traverse the left subtree, then root and then right subtree.
Implementation —
def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
ans = []
def ino(root):
if not root:
return
ino(root.left)
ans.append(root.val)
ino(root.right)
ino(root)
return ansQuestion Link
Similar Pattern —
Convert Binary Search Tree to Sorted Doubly Linked List
Minimum Distance Between BST Nodes
Closest Binary Search Tree Value II
Full Code Video Explanation ( In progress. Subscribe today for updates) :
— — — — — — — — — — — — — — — — — — — — — — — — — — — — — — —
Maximum Depth of Binary Tree
Question —
Given the root of a binary tree, return its maximum depth.
A binary tree’s maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.
Example :
Input: root = [3,9,20,null,null,15,7]
Output: 3Solution :
Main Logic/Idea —
The main idea is to calculate the depth of left subtree and right subtree and then choose whichever is max ( add 1 to it).
Implementation —
def maxDepth(self, root: Optional[TreeNode]) -> int:
if not root: return 0
return 1+ max((self.maxDepth(root.left)), (self.maxDepth(root.right)))Question Link
Similar Pattern —
Time Needed to Inform All Employees
Amount of Time for Binary Tree to Be Infected
Full Code Video Explanation ( In progress. Subscribe today for updates) :
Note : New Recursion with solutions will be added everyday. So keep checking this post daily.
Tips and Techniques to solve Recursion Questions Fast —
Remember the gist of recursion problem is that recursion function solves a problem by calling a copy of itself and dividing and solving smaller subproblems of the original problem.
Always remember to define a base case ( which is like the termination condition).
That’s it for now. Day 10 : Divide and Conquer Technique coming soon !
Let me know if you have questions in the comment section below. Subscribe/ Follow, Like/Clap as it will encourage me to write more in my free time and Stay Tuned!!
Read More —
11 most important System Design Base Concepts
6. Networking, How Browsers work, Content Network Delivery ( CDN)
13. System Design Template — How to solve any System Design Question
Some of the other best Series —
30 days of Data Structures and Algorithms and System Design Simplified
Data Science and Machine Learning Research ( papers) Simplified **
100 days : Your Data Science and Machine Learning Degree Series with projects
Complete Data Visualization and Pre-processing Series with projects
Exceptional Github Repos — Part 1
Exceptional Github Repos — Part 2
Tech Newsletter —
If you are interested, you can join my newsletter through which I send tech interview tips, techniques, patterns, hacks — Software Development, ML, Data Science, Startups and Technology projects to more than 30K readers. You can subscribe to Tech Brew :
For Python Projects —
For complete 60 days of Data Science and ML : Day 1 — Day 60 : Quick Recap of 60 days of Data Science and ML
Follow for more updates. Stay tuned and keep coding!
For other projects, tune to —
Build Machine Learning Pipelines( With Code)
Recurrent Neural Network with Keras
Clustering Geolocation Data in Python using DBSCAN and K-Means
Facial Expression Recognition using Keras
Hyperparameter Tuning with Keras Tuner
Custom Layers in Keras
