Topic: Mastering Recursion — From Basics to Advanced Applications

---

What is Recursion?

• Recursion is a technique where a function calls itself to solve smaller instances of a problem until reaching a base case.

---

Basic Structure

• Every recursive function needs:

* A base case to stop recursion.

* A recursive case that breaks the problem into smaller parts.

---

Simple Example: Fibonacci Numbers

def fibonacci(n):
    if n <= 1:
        return n  # base case
    else:
        return fibonacci(n-1) + fibonacci(n-2)  # recursive case

---

Drawbacks of Naive Recursion

• Repeated calculations cause exponential time complexity.

• Can cause stack overflow on large inputs.

---

Improving Recursion: Memoization

• Store results of subproblems to avoid repeated work.

memo = {}
def fib_memo(n):
    if n in memo:
        return memo[n]
    if n <= 1:
        memo[n] = n
    else:
        memo[n] = fib_memo(n-1) + fib_memo(n-2)
    return memo[n]

---

Advanced Concepts

• Tail Recursion: Recursive call is the last operation. Python does not optimize tail calls but understanding it is important.

• Divide and Conquer Algorithms: Recursion breaks problems into subproblems (e.g., Merge Sort, Quick Sort).

---

Example: Merge Sort

def merge_sort(arr):
    if len(arr) <= 1:
        return arr

    mid = len(arr) // 2
    left = merge_sort(arr[:mid])
    right = merge_sort(arr[mid:])

    return merge(left, right)

def merge(left, right):
    result = []
    i = j = 0

    while i < len(left) and j < len(right):
        if left[i] < right[j]:
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1

    result.extend(left[i:])
    result.extend(right[j:])
    return result

---

Exercise

• Implement a recursive function to solve the Tower of Hanoi problem for *n* disks and print the moves.

---

#Algorithms #Recursion #Memoization #DivideAndConquer #CodingExercise

https://t.iss.one/DataScience4

Topic: Data Structures – Trees – Top 15 Interview Questions with Answers

---

### 1. What is a tree data structure?

A hierarchical structure with nodes connected by edges, having a root node and child nodes with no cycles.

---

### 2. What is the difference between binary tree and binary search tree (BST)?

A binary tree allows up to two children per node; BST maintains order where left child < node < right child.

---

### 3. What are the types of binary trees?

Full, perfect, complete, skewed (left/right), and balanced binary trees.

---

### 4. Explain tree traversal methods.

Inorder (LNR), Preorder (NLR), Postorder (LRN), and Level Order (BFS).

---

### 5. What is a balanced tree? Why is it important?

A tree where the height difference between left and right subtrees is minimal to ensure O(log n) operations.

---

### 6. What is an AVL tree?

A self-balancing BST maintaining balance factor (-1, 0, 1) with rotations to balance after insert/delete.

---

### 7. What are rotations in AVL trees?

Operations (Left, Right, Left-Right, Right-Left) used to rebalance the tree after insertion or deletion.

---

### 8. What is a Red-Black Tree?

A balanced BST with red/black nodes ensuring balance via color rules, offering O(log n) operations.

---

### 9. How does a Trie work?

A tree structure used for storing strings, where nodes represent characters, allowing fast prefix searches.

---

### 10. What is the height of a binary tree?

The number of edges on the longest path from root to a leaf node.

---

### 11. How do you find the lowest common ancestor (LCA) of two nodes?

By traversing from root, checking if nodes lie in different subtrees, or by storing parent pointers.

---

### 12. What is the difference between DFS and BFS on trees?

DFS explores as far as possible along branches; BFS explores neighbors level by level.

---

### 13. How do you detect if a binary tree is a BST?

Check if inorder traversal yields a sorted sequence or verify node values within valid ranges recursively.

---

### 14. What are leaf nodes?

Nodes with no children.

---

### 15. How do you calculate the number of nodes in a complete binary tree?

Using the formula: number\_of\_nodes = 2^(height + 1) - 1 (if perfect), else traverse and count.

---

### Exercise

Write functions for inorder, preorder, postorder traversals, check if tree is BST, and find LCA of two nodes.

---

#DSA #Trees #InterviewQuestions #BinaryTrees #Python #Algorithms

https://t.iss.one/DataScience4