Scribd
Upload
4 views1 page

Print: None None

The document contains code snippets for various data structures and algorithms, including binary trees, depth-first search (DFS), breadth-first search (BFS), binary search, and trie implementation. It demonstrates recursive and iterative approaches for tree traversal, searching, and sorting techniques like merge sort. Additionally, it includes utility functions for array manipulation and string operations such as palindrome checking.

Uploaded by

felipperoza
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
4 views1 page

Print: None None

The document contains code snippets for various data structures and algorithms, including binary trees, depth-first search (DFS), breadth-first search (BFS), binary search, and trie implementation. It demonstrates recursive and iterative approaches for tree traversal, searching, and sorting techniques like merge sort. Additionally, it includes utility functions for array manipulation and string operations such as palindrome checking.

Uploaded by

felipperoza
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 1

Print

# Binary tree
class TreeNode:
def __init__(self, val): def dfs_recursive(graph, node, visited=None):
self.val = val if visited is None:
self.left = None visited = set()
self.right = None visited.add(node)
# Inorder traversal (recursive) print(node, end=" ") # Process the node (e.g., print it)
def inorder(node): for neighbor in graph[node]:
if node: if neighbor not in visited: #search in sets O(1) in avg. WC O(n)
inorder(node.left) dfs_recursive(graph, neighbor, visited)
print(node.val) from collections import deque
inorder(node.right)
def bfs(graph, start):
# Binary search O(log n)/O(1) visited = set() # To track visited nodes
# Condition: arr must be sorted queue = deque([start]) # Initialize queue with the starting node
def binary_search(arr, target): result = [] # To store the order of traversal
left = 0 while queue:
right = len(arr) - 1 node = queue.popleft() # Dequeue the first element
while left <= right: if node not in visited:
mid = (left + right) // 2 visited.add(node) # Mark as visited
if arr[mid] == target: result.append(node) # Add to result
return mid queue.extend(graph[node]) # Enqueue all unvisited neighbors
if arr[mid] < target: return result
left = mid + 1 # 208. Implement Trie (Prefix Tree)
if arr[mid] > target: class Node:
right = mid - 1 def __init__(self):
return -1 # no match self.children = {}
self.isTerminal = False
## Arrays and strings class Trie(object):
def reverse_array(arr): def __init__(self):
return arr[::-1] self.root = Node()
def is_palindrome(s): def insert(self, word):
return s == s[::-1] node = self.root
for c in word:
if c not in node.children:
# Merge sort (recurs) O(n logn)/O(n) node.children[c] = Node()
def merge_sort(arr):
node = node.children[c]
if len(arr) <= 1:
node.isTerminal = True
return arr def search(self, word):
mid = len(arr) // 2
node = self.root
left = merge_sort(arr[:mid])
for c in word:
right = merge_sort(arr[mid:]) if c not in node.children:
print(left, right) return False
return(merge(left, right))
node = node.children[c]
def merge(left, right): return node.isTerminal
result = []
i = 0
def startsWith(self, prefix):
j = 0 node = self.root
while i<len(left) and j<len(right): for c in prefix:
if left[i] <= right[j]:
if c not in node.children:
result.append(left[i])
return False
i+=1 node = node.children[c]
else:
return True
result.append(right[j])
j+=1
result += left[i:]
result += right[j:]
return result

You might also like