Trees and Heaps (Data Structures & Algorithms)

Title: Trees and Heaps (Data Structures & Algorithms) - A full guide Using Python Examples

Why This Matters

Understanding data structures like trees and heaps is crucial for solving complex problems, especially during coding interviews and competitive programming contests. These data structures help optimize algorithms by providing efficient ways to store and retrieve data. In this lesson, we will learn about various types of trees (Binary Trees, AVL Trees, Binary Search Trees, Trie) and Heaps (Max Heap, Min Heap). We'll look closely at their implementations using Python examples, common mistakes, practice questions, and frequently asked questions.

Prerequisites

To follow this lesson, you should have a good understanding of the following concepts:

1. Basic Python syntax (variables, loops, functions)
2. Recursion
3. Data structures (arrays, lists, dictionaries)
4. Big O notation
5. Understanding of basic sorting algorithms like Selection Sort, Bubble Sort, and Quick Sort.
6. Familiarity with binary operations such as max(), min(), len(), and comparison operators (<, >, <=, >=).
7. Knowledge of Python's built-in functions like append(), pop(), and sorted().

Core Concept

Trees

A tree is a hierarchical data structure consisting of nodes and edges. Each node has zero or more children, except for the root node, which may have no parent. In computer science, we primarily focus on binary trees, where each node has at most two children (left child and right child).

Binary Trees

A binary tree is a tree in which each node has at most two children. The left child is smaller than the parent, while the right child is larger or equal to the parent.

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

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

AVL Trees

AVL (Adelson-Velsky and Landis) trees are self-balancing binary search trees. They ensure that the height of the left and right subtrees differs by at most one. This property allows for efficient insertion, deletion, and search operations.

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

def get_height(node):
if node is None:
return 0
return node.height

def update_height(node):
node.height = max(get_height(node.left), get_height(node.right)) + 1

... (insert, delete, rotate functions)

#### Binary Search Trees

A binary search tree is a binary tree data structure where each node's key value is greater than or equal to the keys in its left subtree and less than or equal to the keys in its right subtree. This property allows for efficient search, insertion, and deletion operations.

class Node:

def __init__(self, key):

self.key = key

self.left = None

self.right = None

def min_value(node):

current = node

while current.left is not None:

current = current.left

return current

def insert(root, key):

if root is None:

return Node(key)

else:

if key < root.key:

root.left = insert(root.left, key)

elif key > root.key:

root.right = insert(root.right, key)

return root

#### Trie

A trie (prefix tree) is a tree data structure used to efficiently store and retrieve keys in a dynamic set or associative array where all keys have a common prefix.

class Node:

def __init__(self):

self.children = {}

self.is_end_of_word = False

def insert(root, key):

node = root

for char in key:

if char not in node.children:

node.children[char] = Node()

node = node.children[char]

node.is_end_of_word = True

### Heaps

A heap is a complete binary tree where each parent node's key value is greater than or equal to (for max heap) or less than or equal to (for min heap) its children's keys. This property allows for efficient sorting and priority queue operations.

class Heap:

def __init__(self, arr):

self.heap = arr[:]

self.build_heap(self.heap)

def build_heap(self, heap):

n = len(heap)

for i in range(n // 2 - 1, -1, -1):

self.heapify(heap, i, n)

def heapify(self, heap, i, n):

largest = i

l = 2 * i + 1

r = 2 * i + 2

if l < n and heap[largest] < heap[l]:

largest = l

if r < n and heap[largest] < heap[r]:

largest = r

if largest != i:

self.heap[i], self.heap[largest] = self.heap[largest], self.heap[i]

self.heapify(heap, largest, n)

Worked Example

Let's implement a Binary Search Tree and perform some common operations like insertion, deletion, search, and inorder traversal.

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

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

def min_value(node):
current = node
while current.left is not None:
current = current.left
return current

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:
if root.left is None:
return root.right
elif root.right is None:
return root.left

temp_val = root.min_value(root.right).key
root.key = temp_val
root.right = delete(root.right, temp_val)
return root

def inorder_traversal(node):
if node is not None:
inorder_traversal(node.left)
print(node.key, end=" ")
inorder_traversal(node.right)

Common Mistakes

1. Forgetting to update the height of a node after insertion or deletion in AVL trees.
2. Not properly handling duplicate keys during insertion in Binary Search Trees and Heaps.
3. Misunderstanding the concept of a complete binary tree for heap operations.
4. Failing to maintain the property of a binary search tree (left subtree less than parent, right subtree greater than or equal to parent).
5. Not properly handling cases where a node has only one child during deletion in Binary Search Trees and Heaps.
6. In AVL trees, forgetting to rebalance the tree after inserting/deleting a node that violates the height difference property.
7. In Trie, not considering the case when a word is being inserted for the first time (i.e., no common prefix exists).

Practice Questions

1. Implement an AVL Tree with insert, delete, and height functions.
2. Write a function to find the minimum depth of a binary tree.
3. Implement a Trie data structure with insert, search, and delete operations.
4. Write a Python function to convert a given Binary Tree into a Doubly Linked List in order of traversal.
5. Implement a Min Heap and Max Heap using arrays.
6. Implement a function that checks if two binary trees are identical.
7. Implement a function that finds the common ancestors between two nodes in a binary search tree.
8. Implement a function to find the lowest common ancestor (LCA) of two nodes in a given AVL tree.
9. Implement a function to find the kth smallest element in a Binary Search Tree.
10. Implement a function to merge two sorted arrays into a single sorted array using a binary search tree.

FAQ

What is the time complexity for inserting an element in a binary search tree?

• O(log n) on average, but it can be as bad as O(n) in the worst case (e.g., if the tree is skewed).

How do I find the maximum value in a binary search tree without using recursion?

• You can use an iterative approach by traversing the tree and keeping track of the maximum value found so far.

What is the time complexity for searching an element in a trie data structure?

• O(m), where m is the length of the key being searched.

How do I convert a binary tree into a sorted array (in-order traversal)?

• You can use recursion to perform an in-order traversal and store the values in a list.

What is the time complexity for deleting an element from a min heap?

• O(log n) on average, but it can be as bad as O(n) in the worst case (e.g., if the tree becomes unbalanced during deletion).

How do I find the kth smallest element in a binary heap?

• You can maintain a min heap of size k that stores the k smallest elements found so far, and update it after each insertion or deletion operation.

What is the time complexity for finding the common ancestors between two nodes in a binary search tree?

• O(log n) on average, but it can be as bad as O(n) in the worst case (e.g., if the tree is skewed).

What is the time complexity for finding the lowest common ancestor (LCA) of two nodes in a given AVL tree?

• O(log n) on average, but it can be as bad as O(n) in the worst case (e.g., if the tree is skewed).