📚 Data Structures and Algorithms with Go (2024)

1⃣ Join Channel Download:
https://t.me/+MhmkscCzIYQ2MmM8

2⃣ Download Book: https://t.me/c/1854405158/1410

💬 Tags: #DSA #GO

👉 BEST DATA SCIENCE CHANNELS ON TELEGRAM 👈

📚 Data Structures the Fun Way (2024)

1⃣ Join Channel Download:
https://t.me/+MhmkscCzIYQ2MmM8

2⃣ Download Book: https://t.me/c/1854405158/1611

💬 Tags: #DSA

👉 BEST DATA SCIENCE CHANNELS ON TELEGRAM 👈

📚 Python Exercises with Data Structures and Algorithms (2024)

1⃣ Join Channel Download:
https://t.me/+MhmkscCzIYQ2MmM8

2⃣ Download Book: https://t.me/c/1854405158/1646

💬 Tags: #DSA

👉 BEST DATA SCIENCE CHANNELS ON TELEGRAM 👈

📚 Algorithms and Data Structures with Python (2024)

1⃣ Join Channel Download:
https://t.me/+MhmkscCzIYQ2MmM8

2⃣ Download Book: https://t.me/c/1854405158/1676

💬 Tags: #DSA

👉 BEST DATA SCIENCE CHANNELS ON TELEGRAM 👈

📚 Data Structure and Algorithm (2024)

1⃣ Join Channel Download:
https://t.me/+MhmkscCzIYQ2MmM8

2⃣ Download Book: https://t.me/c/1854405158/1818

💬 Tags: #DSA

USEFUL CHANNELS FOR YOU

📚 Data Structure in Python (2024)

1⃣ Join Channel Download:
https://t.me/+MhmkscCzIYQ2MmM8

2⃣ Download Book: https://t.me/c/1854405158/1827

💬 Tags: #dsa

USEFUL CHANNELS FOR YOU

📚 Python Data Structures and Algorithms (2017)

1⃣ Join Channel Download:
https://t.me/+MhmkscCzIYQ2MmM8

2⃣ Download Book: https://t.me/c/1854405158/1954

💬 Tags: #DSA

USEFUL CHANNELS FOR YOU

Topic: Linked Lists in Python – Part 1: Introduction and Singly Linked List Basics

---

What is a Linked List?

• A linked list is a linear data structure where each element (called a node) contains:

• The data value.
• A pointer (or reference) to the next node.

• Unlike arrays, linked lists don’t require contiguous memory and can grow dynamically.

---

Why Use Linked Lists?

• Efficient insertions/deletions at the beginning or middle.
• No need for pre-defining size, unlike arrays.
• Used in memory-efficient applications like OS kernels, compilers, and real-time systems.

---

Types of Linked Lists

• Singly Linked List – Each node points to the next.
• Doubly Linked List – Nodes have next and previous pointers.
• Circular Linked List – The last node points back to the head.

---

Basic Structure of a Node

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

---

Building a Singly Linked List

class LinkedList:
    def __init__(self):
        self.head = None

    def append(self, data):
        new_node = Node(data)

        if not self.head:
            self.head = new_node
            return

        current = self.head
        while current.next:
            current = current.next
        current.next = new_node

---

Traversing the List

def display(self):
    current = self.head
    while current:
        print(current.data, end=" -> ")
        current = current.next
    print("None")

Usage:

ll = LinkedList()
ll.append(10)
ll.append(20)
ll.append(30)
ll.display()  # Output: 10 -> 20 -> 30 -> None

---

Inserting at the Beginning

def insert_at_beginning(self, data):
    new_node = Node(data)
    new_node.next = self.head
    self.head = new_node

---

Summary

• A singly linked list stores data as a sequence of nodes linked by references.

• Supports dynamic memory usage, fast insertions, and flexible resizing.

• The key is managing node connections safely and efficiently.

---

Exercise

• Implement a method length() that returns the number of nodes in the list.

---

#DataStructures #LinkedList #DSA #Python #CodingBasics

https://t.me/DataScience4

Topic: Linked Lists in Python – Part 2: Insertion, Deletion, and Search Operations

---

Recap from Part 1

• A singly linked list consists of nodes, where each node holds data and a pointer to the next node.

• We've implemented basic append and display functions.

Now we’ll explore insertion at specific positions, deletion, and searching.

---

1. Insert at a Specific Position

def insert_at_position(self, index, data):
    if index < 0:
        raise IndexError("Index cannot be negative")
    
    new_node = Node(data)
    
    if index == 0:
        new_node.next = self.head
        self.head = new_node
        return

    current = self.head
    for _ in range(index - 1):
        if not current:
            raise IndexError("Index out of bounds")
        current = current.next
    
    new_node.next = current.next
    current.next = new_node

---

2. Delete a Node by Value

def delete_by_value(self, value):
    if not self.head:
        return

    if self.head.data == value:
        self.head = self.head.next
        return

    current = self.head
    while current.next and current.next.data != value:
        current = current.next

    if current.next:
        current.next = current.next.next

---

3. Delete a Node by Index

def delete_by_index(self, index):
    if index < 0:
        raise IndexError("Index cannot be negative")

    if not self.head:
        raise IndexError("List is empty")

    if index == 0:
        self.head = self.head.next
        return

    current = self.head
    for _ in range(index - 1):
        if not current.next:
            raise IndexError("Index out of bounds")
        current = current.next

    if current.next:
        current.next = current.next.next

---

4. Search for an Element

def search(self, value):
    current = self.head
    index = 0
    while current:
        if current.data == value:
            return index
        current = current.next
        index += 1
    return -1  # Not found

---

5. Complete Class with All Methods

class LinkedList:
    def __init__(self):
        self.head = None

    def append(self, data): ...
    def display(self): ...
    def insert_at_position(self, index, data): ...
    def delete_by_value(self, value): ...
    def delete_by_index(self, index): ...
    def search(self, value): ...

*(You can reuse the method definitions above.)*

---

Summary

• You can manipulate linked lists with insertions and deletions at any position.

• Searching through a singly linked list is O(n).

• Always check for edge cases: empty list, index bounds, and duplicates.

---

Exercise

• Write a method reverse() that reverses the linked list in-place and test it on a list of 5+ elements.

---

#DSA #LinkedList #Python #Insertion #Deletion #Search

https://t.me/DataScience4

Topic: Linked Lists in Python – Part 3: Reversing, Detecting Loops, and Middle Node

---

In this part, we’ll explore advanced operations that are frequently asked in coding interviews using singly linked lists.

---

1. Reverse a Linked List (Iterative)

def reverse(self):
    prev = None
    current = self.head
    while current:
        next_node = current.next
        current.next = prev
        prev = current
        current = next_node
    self.head = prev

• Time Complexity: O(n)
• Space Complexity: O(1)

---

2. Find the Middle of the Linked List

• Use the slow and fast pointer approach.

def find_middle(self):
    slow = fast = self.head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
    return slow.data if slow else None

---

3. Detect a Loop in the Linked List

• Use Floyd’s Cycle Detection Algorithm (a.k.a. Tortoise and Hare).

def has_loop(self):
    slow = fast = self.head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow == fast:
            return True
    return False

---

4. Find the N-th Node from the End

def nth_from_end(self, n):
    first = self.head
    second = self.head

    for _ in range(n):
        if not first:
            return None
        first = first.next

    while first:
        first = first.next
        second = second.next

    return second.data

---

5. Full Example: Testing All Methods

ll = LinkedList()
for value in [10, 20, 30, 40, 50]:
    ll.append(value)

ll.display()
ll.reverse()
ll.display()
print("Middle:", ll.find_middle())
print("Has Loop?", ll.has_loop())
print("3rd from End:", ll.nth_from_end(3))

---

Summary

• Use pointer manipulation for efficient algorithms in linked lists.

• Common techniques:
• Fast/slow pointers
• Reversal by in-place re-linking
• Two-pointer gap approach for nth from end

---

Exercise

• Write a method is_palindrome() that checks if the linked list reads the same forwards and backwards (without converting it to a list or using extra space).

---

#DSA #LinkedList #ReverseList #LoopDetection #TwoPointerTechnique

https://t.me/DataScience4

Topic: Linked Lists in Python – Part 4: Merging, Sorting, and Advanced Interview Problems

---

In this final part of the Linked List series, we’ll tackle more advanced and practical use cases like merging sorted lists, sorting a linked list, and interview-level challenges.

---

1. Merging Two Sorted Linked Lists

def merge_sorted_lists(l1, l2):
    dummy = Node(0)
    tail = dummy

    while l1 and l2:
        if l1.data < l2.data:
            tail.next = l1
            l1 = l1.next
        else:
            tail.next = l2
            l2 = l2.next
        tail = tail.next

    tail.next = l1 or l2
    return dummy.next

---

2. Sorting a Linked List (Merge Sort – O(n log n))

def merge_sort(head):
    if not head or not head.next:
        return head

    # Split list
    slow, fast = head, head.next
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next

    mid = slow.next
    slow.next = None

    left = merge_sort(head)
    right = merge_sort(mid)

    return merge_sorted_lists(left, right)

• Attach this to your LinkedList class to sort self.head.

---

3. Removing Duplicates from a Sorted List

def remove_duplicates(self):
    current = self.head
    while current and current.next:
        if current.data == current.next.data:
            current.next = current.next.next
        else:
            current = current.next

---

4. Intersection Point of Two Linked Lists

def get_intersection_node(headA, headB):
    if not headA or not headB:
        return None

    a, b = headA, headB
    while a != b:
        a = a.next if a else headB
        b = b.next if b else headA
    return a  # Can be None or the intersecting node

---

5. Flatten a Multilevel Linked List

Imagine a list where each node has next and child pointers. Recursively flatten:

def flatten(node):
    if not node:
        return None

    next_node = node.next
    if node.child:
        child_tail = flatten(node.child)
        node.next = node.child
        node.child = None
        child_tail.next = flatten(next_node)
        return child_tail if child_tail.next else child_tail
    else:
        node.next = flatten(next_node)
        return node

---

Summary

• You now know how to merge, sort, and deduplicate linked lists.

• Techniques like merge sort, two-pointer traversal, and recursive flattening are essential for mastering linked lists.

• These problems are frequently asked in interviews at top tech companies.

---

Exercise

• Given two unsorted linked lists, write a function that returns a new linked list containing only the elements present in both lists (intersection), without using extra space or sets.

---

#DSA #LinkedList #MergeSort #AdvancedDSA #CodingInterview

https://t.me/DataScience4

Topic: Data Structures – Trees – Part 1 of 4: Introduction and Binary Trees

---

### 1. What is a Tree in Data Structures?

A tree is a non-linear hierarchical data structure consisting of nodes connected by edges. It's widely used in real-world applications like:

• File systems
• Databases (e.g., B-Trees)
• Compilers (parse trees)
• Artificial intelligence (decision trees)

---

### 2. Terminologies in Trees

• Node: Basic unit of a tree
• Root: Topmost node (only one)
• Parent/Child: A node that connects to another below/above
• Leaf: A node with no children
• Edge: Connection between parent and child
• Subtree: Any child node and its descendants
• Depth: Distance from the root to a node
• Height: Longest path from a node to a leaf
• Degree: Number of children a node has

---

### 3. Binary Tree Basics

A Binary Tree is a tree in which each node has at most two children, referred to as:

• Left child
• Right child

#### Real-life example:

Imagine a family tree where each person can have two children.

---

### 4. Types of Binary Trees

• Full Binary Tree – every node has 0 or 2 children
• Perfect Binary Tree – all internal nodes have 2 children, and all leaves are at the same level
• Complete Binary Tree – all levels are filled except possibly the last, which is filled from left to right
• Skewed Tree – all nodes only have one child (left or right)
• Balanced Binary Tree – the height difference of left and right subtrees is minimal

---

### 5. Binary Tree Representation in Python

Using Class & Object:

class Node:
    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None

# Example
root = Node(1)
root.left = Node(2)
root.right = Node(3)

---

### 6. Tree Traversals

Tree traversal means visiting all the nodes of a tree in a specific order.

• Inorder (LNR)
• Preorder (NLR)
• Postorder (LRN)
• Level Order (BFS using queue)

#### Example – Inorder Traversal (Left → Root → Right):

def inorder(root):
    if root:
        inorder(root.left)
        print(root.data, end=" ")
        inorder(root.right)

---

### 7. Build a Simple Binary Tree and Traverse It

# Tree Structure:
#      1
#     / \
#    2   3
#   / \
#  4   5

root = Node(1)
root.left = Node(2)
root.right = Node(3)
root.left.left = Node(4)
root.left.right = Node(5)

print("Inorder Traversal:")
inorder(root)  # Output: 4 2 5 1 3

---

### 8. Applications of Binary Trees

• Expression evaluation
• Search algorithms (Binary Search Trees)
• Priority queues (Heaps)
• Huffman encoding trees (data compression)
• Syntax trees in compilers

---

### 9. Key Characteristics

• Recursive nature makes tree problems suitable for recursion
• Not sequential – can't be represented with only arrays or lists
• Memory-efficient using pointers in linked structure

---

### 10. Summary

• Trees are hierarchical and non-linear
• Binary trees limit nodes to max 2 children
• Various types of binary trees serve different use cases
• Tree traversal is fundamental for solving tree problems

---

### Exercise

Create a class-based binary tree and implement:
• Inorder, Preorder, and Postorder traversals
• Function to count total nodes and leaf nodes

---

#DSA #BinaryTree #DataStructures #Python #TreeTraversal

https://t.me/DataScience4

Topic: Data Structures – Trees – Part 2 of 4: Binary Search Trees (BST)

---

### 1. What is a Binary Search Tree (BST)?

A Binary Search Tree (BST) is a binary tree where all nodes follow the below properties:

• The left child of a node contains only nodes with values less than the node's value.
• The right child of a node contains only nodes with values greater than the node's value.
• Both left and right subtrees must also be BSTs.

This property allows for efficient searching, insertion, and deletion.

---

### 2. Why Use BSTs?

• Search operations are faster than in linear structures (like lists).
• Ordered traversal becomes very efficient.
• Time complexity (on average):
 • Search: O(log n)
 • Insert: O(log n)
 • Delete: O(log n)
*Worst case is O(n) for skewed trees.*

---

### 3. Implementing a BST in Python

class Node:
    def __init__(self, key):
        self.key = key
        self.left = None
        self.right = None

#### Insert Function:

def insert(root, key):
    if root is None:
        return Node(key)
    if key < root.key:
        root.left = insert(root.left, key)
    else:
        root.right = insert(root.right, key)
    return root

#### Example Tree:

root = None
for val in [50, 30, 70, 20, 40, 60, 80]:
    root = insert(root, val)

This creates:

        50
       /  \
     30    70
    / \   /  \
  20 40 60  80

---

### 4. Searching in BST

def search(root, key):
    if root is None or root.key == key:
        return root
    if key < root.key:
        return search(root.left, key)
    else:
        return search(root.right, key)

---

### 5. Finding Minimum and Maximum

def find_min(root):
    while root.left:
        root = root.left
    return root.key

def find_max(root):
    while root.right:
        root = root.right
    return root.key

---

### 6. Deleting a Node in BST

There are 3 cases:

1. Node has no children
2. Node has one child
3. Node has two children

def delete(root, key):
    if root is None:
        return root

    if key < root.key:
        root.left = delete(root.left, key)
    elif key > root.key:
        root.right = delete(root.right, key)
    else:
        # Node with only one child or no child
        if root.left is None:
            return root.right
        elif root.right is None:
            return root.left
        # Node with two children
        temp = find_min_node(root.right)
        root.key = temp.key
        root.right = delete(root.right, temp.key)

    return root

def find_min_node(node):
    while node.left:
        node = node.left
    return node

---

### 7. Inorder Traversal of BST

Inorder traversal of a BST gives sorted order:

def inorder(root):
    if root:
        inorder(root.left)
        print(root.key, end=" ")
        inorder(root.right)

---

### 8. Time and Space Complexity Summary

| Operation | Best Case | Average Case | Worst Case |
| --------- | --------- | ------------ | ---------- |
| Search | O(log n) | O(log n) | O(n) |
| Insert | O(log n) | O(log n) | O(n) |
| Delete | O(log n) | O(log n) | O(n) |

*Worst case occurs when tree is skewed (e.g., inserting sorted data)*

---

### 9. Applications of BST

• Search engines
• Sorted maps and sets
• Auto-complete features
• Database indexing
• Tree-based dictionaries

---

### 10. Summary

• BST enforces ordering which helps efficient operations
• Insertion, search, and deletion rely on recursive logic
• Traversals help in data processing
• Performance degrades in unbalanced trees — next part will cover balanced trees

---

### Exercise

• Write code to insert, delete, and search in a BST.
• Traverse the BST in inorder, preorder, and postorder.
• Add a function to count number of nodes and leaf nodes.
• Try inserting sorted data and observe tree structure (hint: use print or drawing).

#DSA #DataStructures #Tree #Python

https://t.me/DataScience4

Topic: Data Structures – Trees – Part 3 of 4: Balanced Trees – AVL Trees & Tree Height Management

---

### 1. Why Balance Matters in Trees

In unbalanced trees, especially skewed trees, operations like search, insert, and delete can degrade to O(n) time complexity.
Balanced trees maintain height close to log(n) for efficient performance.

---

### 2. AVL Tree – Introduction

An AVL Tree is a self-balancing Binary Search Tree named after inventors Adelson-Velsky and Landis.

Properties:

• For every node, the balance factor (height of left subtree – height of right subtree) must be -1, 0, or +1
• Automatically re-balances after insertions and deletions

---

### 3. Balance Factor Calculation

balance = height(left subtree) - height(right subtree)

Cases:

• Balance Factor > 1 → Left-heavy
• Balance Factor < -1 → Right-heavy

---

### 4. Rotations in AVL Trees

To restore balance, AVL trees use rotations:

Single Rotations:

• Right Rotation (LL Case)
• Left Rotation (RR Case)

Double Rotations:

• Left-Right Rotation (LR Case)
• Right-Left Rotation (RL Case)

---

### 5. AVL Tree Node Structure

class Node:
    def __init__(self, key):
        self.key = key
        self.left = None
        self.right = None
        self.height = 1

---

### 6. Helper Functions

def get_height(node):
    if not node:
        return 0
    return node.height

def get_balance(node):
    if not node:
        return 0
    return get_height(node.left) - get_height(node.right)

def right_rotate(z):
    y = z.left
    T3 = y.right

    y.right = z
    z.left = T3

    z.height = 1 + max(get_height(z.left), get_height(z.right))
    y.height = 1 + max(get_height(y.left), get_height(y.right))

    return y

def left_rotate(z):
    y = z.right
    T2 = y.left

    y.left = z
    z.right = T2

    z.height = 1 + max(get_height(z.left), get_height(z.right))
    y.height = 1 + max(get_height(y.left), get_height(y.right))

    return y

---

### 7. Insertion in AVL Tree

def insert(node, key):
    if not node:
        return Node(key)

    if key < node.key:
        node.left = insert(node.left, key)
    elif key > node.key:
        node.right = insert(node.right, key)
    else:
        return node  # no duplicate keys

    # Update height
    node.height = 1 + max(get_height(node.left), get_height(node.right))

    # Get balance factor
    balance = get_balance(node)

    # Balance the tree
    # Case 1 - Left Left
    if balance > 1 and key < node.left.key:
        return right_rotate(node)

    # Case 2 - Right Right
    if balance < -1 and key > node.right.key:
        return left_rotate(node)

    # Case 3 - Left Right
    if balance > 1 and key > node.left.key:
        node.left = left_rotate(node.left)
        return right_rotate(node)

    # Case 4 - Right Left
    if balance < -1 and key < node.right.key:
        node.right = right_rotate(node.right)
        return left_rotate(node)

    return node

---

### 8. Example AVL Tree Construction

root = None
for val in [10, 20, 30, 40, 50, 25]:
    root = insert(root, val)

After insertion, the AVL Tree balances itself using appropriate rotations.

---

### 9. Traversals

Use any standard traversal to see the output:

def inorder(root):
    if root:
        inorder(root.left)
        print(root.key, end=" ")
        inorder(root.right)

---

### 10. Summary

• AVL Trees ensure that BSTs stay balanced
• Balance is maintained using rotations after insertion
• Time complexity for all operations is O(log n)
• AVL Trees are ideal when frequent insertions and deletions are expected

---

### Exercise

• Build an AVL Tree from a set of values
• Add functions for insert, get_height, get_balance, and inorder
• Test insertions that trigger all four types of rotations
• Bonus: Implement AVL deletion (complex but possible)

---

#DSA #BalancedTree #BinarySearchTree #Python

https://t.me/DataScience

Topic: Data Structures – Trees – Part 4 of 4: Advanced Trees – Red-Black Trees and Trie

---

### 1. Introduction

This part covers two advanced and widely used tree data structures:

• Red-Black Trees – balanced search trees
• Trie (Prefix Tree) – efficient string storage and retrieval

---

### 2. Red-Black Trees (RBT)

---

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

A Red-Black Tree is a self-balancing Binary Search Tree with extra color property:

* Each node is either red or black
* Root is always black
* Red nodes cannot have red children (no two reds in a row)
* Every path from root to leaves has the same number of black nodes (black-height)

---

#### Why Red-Black Trees?

* Guarantees O(log n) time for insert, delete, and search
* Slightly less rigid balancing than AVL but faster insertion/deletion
* Used in many libraries (e.g., C++ STL map/set)

---

#### Key Properties Recap

1. Every node is red or black
2. Root is black
3. Red nodes have black children
4. Every path from root to null leaves contains same black nodes count

---

#### Basic Operations

* Insertions and deletions are followed by color adjustments and rotations
* Ensures tree remains balanced with Red-Black properties intact

---

### 3. Trie (Prefix Tree)

---

#### What is a Trie?

A Trie is a tree-like data structure used to store a dynamic set of strings, where:

* Each node represents a character
* Path from root to leaf forms a word
* Used for prefix searches efficiently

---

#### Why Use a Trie?

• Fast lookup for words and prefixes
• Auto-complete features
• Spell checking
• IP routing (longest prefix matching)

---

#### Trie Node Structure (Python)

class TrieNode:
    def __init__(self):
        self.children = {}
        self.is_end_of_word = False

---

#### Basic Operations

Insert Word:

def insert(root, word):
    node = root
    for char in word:
        if char not in node.children:
            node.children[char] = TrieNode()
        node = node.children[char]
    node.is_end_of_word = True

Search Word:

def search(root, word):
    node = root
    for char in word:
        if char not in node.children:
            return False
        node = node.children[char]
    return node.is_end_of_word

---

### 4. Example Usage of Trie

root = TrieNode()
insert(root, "hello")
insert(root, "helium")

print(search(root, "hello"))  # True
print(search(root, "hel"))    # False (prefix only)

---

### 5. Advantages and Disadvantages

| Data Structure | Advantages | Disadvantages |
| -------------- | -------------------------------------- | ------------------------------- |
| Red-Black Tree | Balanced, efficient search and update | Complex implementation |
| Trie | Fast prefix search and auto-completion | Memory-heavy with many children |

---

### 6. Summary

* Red-Black Trees and AVL Trees both keep BSTs balanced but with different balancing rules
* Tries are specialized for string data, enabling efficient prefix operations
* Both structures are essential for advanced algorithms and systems

---

### 7. Exercise

• Implement basic Red-Black Tree insertion (research needed)
• Implement delete operation in Trie
• Use Trie to implement a simple autocomplete function
• Compare search time for BST vs Trie on string data sets

---

#DSA #RedBlackTree #Trie #AdvancedTrees #DataStructures #Python

https://t.me/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.me/DataScience4