Suppose you want to buy a Big Mac from McDonald's drive-through. There seems to be an endless line in front of you, and you want to know how many cars are in front of yours so you can have the Big Mac before it goes out of stock. You ask the person in the car before yours, but he doesn’t know the answer, so he asks the person in the car in front of him. This goes on until it reaches the first car. The person in the first car tells the person in the second car that he is in spot one. The second car’s owner easily calculates that he is in spot two and tells the third car’s owner his spot number until the car in front of you tells you that he is in spot 99. Now you know you are in spot 100.
This is how recursion works. Instead of solving a big problem one time, you focus on solving the smallest version of the same problem and then recursively call the same function to solve a slightly bigger problem each time until you get the answer to your question. The smallest version of the problem is called the base case, while a function that calls itself, again and again, is the recursive case.
Below are some leetcode problem illustrations on how recursion can elegantly solve coding problems.
https://leetcode.com/problems/search-in-a-binary-search-tree/
class Solution:
def searchBST(self, root: Optional[TreeNode], val: int) -> Optional[TreeNode]:
if root is None or root.val == val:
return root
return self.searchBST(root.left, val) if root.val > val else self.searchBST(root.right, val)
https://leetcode.com/problems/range-sum-of-bst/
class Solution:
def rangeSumBST(self, root: Optional[TreeNode], low: int, high: int) -> int:
if root is None:
return 0
if low <= root.val <= high:
return root.val + self.rangeSumBST(root.left, low, high) + self.rangeSumBST(root.right, low, high)
elif root.val > high:
return self.rangeSumBST(root.left, low, high)
else:
return self.rangeSumBST(root.right, low, high)
https://leetcode.com/problems/two-sum-iv-input-is-a-bst/
class Solution:
def findTarget(self, root: Optional[TreeNode], k: int) -> bool:
seen = set()
def helper(node, k):
if node is None:
return False
otherNum = k - node.val
if otherNum in seen:
return True
seen.add(node.val)
return helper(node.left, k) or helper(node.right, k)
return helper(root, k)
https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-search-tree/
class Solution:
def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
if p.val > root.val and q.val > root.val:
return self.lowestCommonAncestor(root.right, p, q)
elif p.val < root.val and q.val < root.val:
return self.lowestCommonAncestor(root.left, p, q)
else:
return root
https://leetcode.com/problems/merge-two-binary-trees/
class Solution:
def mergeTrees(self, root1: Optional[TreeNode], root2: Optional[TreeNode]) -> Optional[TreeNode]:
if root1 is None and root2 is None:
return None
if root1 is None and root2 is not None:
return root2
if root1 is not None and root2 is None:
return root1
new_node = TreeNode()
new_node.val = root1.val + root2.val
new_node.left = self.mergeTrees(root1.left, root2.left)
new_node.right = self.mergeTrees(root1.right, root2.right)
return new_node
https://leetcode.com/problems/leaf-similar-trees/
class Solution:
def leafSimilar(self, root1: Optional[TreeNode], root2: Optional[TreeNode]) -> bool:
root1arr = []
root2arr = []
def helper(root, arr):
if root is None:
return 0
if root.left is None and root.right is None:
arr.append(root.val)
helper(root.left, arr)
helper(root.right, arr)
helper(root1, root1arr)
helper(root2, root2arr)
return root1arr == root2arr
https://leetcode.com/problems/path-sum/
class Solution:
def hasPathSum(self, root: Optional[TreeNode], targetSum: int) -> bool:
if root is None:
return False
if root.left is None and root.right is None and root.val == targetSum:
return True
return self.hasPathSum(root.left, targetSum - root.val) or self.hasPathSum(root.right, targetSum - root.val)
https://leetcode.com/problems/binary-tree-paths/
class Solution:
def binaryTreePaths(self, root: Optional[TreeNode]) -> List[str]:
ans = []
def helper(root, temp):
if root is None:
return []
if root.left is None and root.right is None:
return ans.append(temp + str(root.val))
temp += str(root.val) + "->"
helper(root.left, temp)
helper(root.right, temp)
helper(root, "")
return ans
https://leetcode.com/problems/symmetric-tree/
class Solution:
def isSymmetric(self, root: Optional[TreeNode]) -> bool:
if root is None:
return True
def helper(root1, root2):
if root1 is None and root2 is None:
return True
if root1 is None or root2 is None:
return False
return root1.val == root2.val and helper(root1.left, root2.right) and helper(root1.right, root2.left)
return helper(root.left, root.right)
https://leetcode.com/problems/closest-binary-search-tree-value/
class Solution:
def closestValue(self, root: Optional[TreeNode], target: float) -> int:
self.closestVal = root.val
def helper(root):
if root is None:
return
if abs(root.val - target) < abs(self.closestVal - target):
self.closestVal = root.val
if root.val > target:
helper(root.left)
else:
helper(root.right)
helper(root)
return self.closestVal
https://leetcode.com/problems/find-all-the-lonely-nodes/
class Solution:
def getLonelyNodes(self, root: Optional[TreeNode]) -> List[int]:
lonelynodes = []
def helper(root, prev):
if root is None:
return None
if prev:
if root == prev.left and prev.right is None:
lonelynodes.append(root.val)
if root == prev.right and prev.left is None:
lonelynodes.append(root.val)
prev = root
helper(root.left, prev)
helper(root.right, prev)
helper(root, None)
return lonelynodes
https://leetcode.com/problems/sum-of-left-leaves/
class Solution:
def sumOfLeftLeaves(self, root: Optional[TreeNode]) -> int:
self.total = 0
if root.left is None and root.right is None:
return 0
def helper(root, prev):
if root is None:
return 0
if root.left is None and root.right is None and root == prev.left:
self.total += root.val
helper(root.left, root)
helper(root.right, root)
helper(root, root)
return self.total
https://leetcode.com/problems/kth-smallest-element-in-a-bst/
class Solution:
def kthSmallest(self, root: Optional[TreeNode], k: int) -> int:
self.ans = None
self.k = k
def helper(root):
if root is None:
return
helper(root.left)
self.k -= 1
if self.k == 0:
self.ans = root.val
return
helper(root.right)
helper(root)
return self.ans
https://leetcode.com/problems/subsets/
class Solution:
def subsets(self, nums: List[int]) -> List[List[int]]:
ans = []
temp = []
def helper(index, temp):
if index == len(nums):
return ans.append(temp)
helper(index + 1, temp + [nums[index]])
helper(index + 1, temp)
helper(0, temp)
return ans
https://leetcode.com/problems/word-break-ii/
class Solution:
def wordBreak(self, s: str, wordDict: List[str]) -> List[str]:
self.ans = []
def helper(temp, s):
if len(s) == 0:
self.ans.append(temp.strip())
for i in range(1, len(s) + 1):
if s[:i] in wordDict:
new_temp = temp + " " + s[:i]
helper(new_temp, s[i:])
helper("", s)
return self.ans
https://leetcode.com/problems/palindrome-partitioning/
class Solution:
def partition(self, s: str) -> List[List[str]]:
ans = []
def helper(temp, s):
if len(s) == 0:
return ans.append(temp)
for i in range(len(s)):
part = s[: i + 1]
if part == part[:: -1]:
helper(temp + [part], s[i + 1:])
helper([], s)
return ans
https://leetcode.com/problems/letter-combinations-of-a-phone-number/
class Solution:
def letterCombinations(self, digits: str) -> List[str]:
if digits == "":
return []
lookup = {
"2": "abc",
"3": "def",
"4": "ghi",
"5": "jkl",
"6": "mno",
"7": "pqrs",
"8": "tuv",
"9": "wxyz"
}
ans = []
def helper(temp, index):
if index == len(digits):
return ans.append(temp)
for i in lookup[digits[index]]:
helper(temp + str(i), index + 1)
helper("", 0)
return ans
https://leetcode.com/problems/generate-parentheses/
class Solution:
def generateParenthesis(self, n: int) -> List[str]:
ans = []
def helper(temp, nob, ncb):
if nob > n or ncb > n or ncb > nob:
return
if nob == ncb == n:
return ans.append(temp)
helper(temp + "(", nob + 1, ncb)
helper(temp + ")", nob, ncb + 1)
helper("", 0, 0)
return ans