Data Structure and Algorithm 4 | Walking and Searching

1. Walking Algorithms

(1) Array Walking

Time complexity $O(n)$.

1
def walkArray(a):
2
    for i in range(len(a)):
3
        print(a[i])

(2) 2D Array (Matrix) Walking

Time complexity $O(n^2)$.

xxxxxxxxxx
4
1
def walkMatrix(a):
2
    for i in range(len(a)):
3
        for j in range(len(a[0])):
4
            print(a[i][j])

(3) Linked List Walking

Time complexity $O(n)$.

xxxxxxxxxx
5
1
def walkLinkedList(root):
2
    p = root
3
    while p:
4
        print(p.val)
5
        p = p.next

(4) Pre-Order Tree Walking (DFS)

Suppose we have a tree of,

xxxxxxxxxx
5
1
              1
2
           /     \   
3
         2         3
4
       /   \     /
5
      4     5   6

Then the pre-order output should be a sequence of,

xxxxxxxxxx
1
1
[1, 2, 4, 5, 3, 6]

Time complexity $O(n)$,

xxxxxxxxxx
5
1
def preorderTraversal(root):
2
    if not root: return
3
    print(root.val)
4
    if root.left: preorderTraversal(root.left)
5
    if root.right: preorderTraversal(root.right)

(6) In-Order Tree Walking (DFS)

See leetcode 94.

Suppose we have a tree of,

xxxxxxxxxx
5
1
              1
2
           /     \   
3
         2         3
4
       /   \     /
5
      4     5   6

Then the in-order output should be a sequence of,

xxxxxxxxxx
1
1
[4, 2, 5, 1, 6, 3]

Time complexity $O(n)$,

xxxxxxxxxx
5
1
def inorderTraversal(root):
2
    if not root: return
3
    if root.left: preorderTraversal(root.left)
4
    print(root.val)
5
    if root.right: preorderTraversal(root.right)

(7) Post-Order Tree Walking (DFS)

Suppose we have a tree of,

xxxxxxxxxx
5
1
              1
2
           /     \   
3
         2         3
4
       /   \     /
5
      4     5   6

Then the post-order output should be a sequence of,

xxxxxxxxxx
1
1
[4, 5, 2, 6, 3, 1]

Time complexity $O(n)$,

xxxxxxxxxx
5
1
def postorderTraversal(root):
2
    if not root: return
3
    if root.left: preorderTraversal(root.left)
4
    if root.right: preorderTraversal(root.right)
5
    print(root.val)

(8) Walking DAG (DFS)

Directed acyclic graph are the simplest graph that we can walk through without cycles.

Time complexity $O(n)$.

xxxxxxxxxx
5
1
def walkDAG(root):
2
    if not root: return
3
    print(root.val)
4
    for p in root.edges:
5
        walkDAG(p)

(9) Walking Graphs with Cycles (DFS)

We should maintain a visited set to record the nodes we have visited and this requires an $O(n)$ space complexity.

Time complexity $O(n)$.

xxxxxxxxxx
7
1
def walkGraph(root, visited: set):
2
    if not root: return
3
    if root in visited: return
4
    visited.add(root)
5
    print(root.val)
6
    for p in root.edges:
7
        walkGraph(p, visited)

Note that the visited can also be a list but searching a list has a higher time complexity than a set. Remember this algorithm works because we are passing the pointer to visited as an argument so that if we make a copy of the set or list we pass, the algorithm will no longer work for us.

xxxxxxxxxx
7
1
def walkGraph(root, visited: set):
2
    if not root: return
3
    if root in visited: return
4
    visited.add(root)
5
    print(root.val)
6
    for p in root.edges:
7
        walkGraph(p, visited.copy())

2. Searching

(1) Searching Sorted Array: Binary Search (Iterations)

Time complexity $O(\log n)$.

xxxxxxxxxx
15
1
def binSearch(a, x):
2
    
3
    left = 0
4
    right = len(a) - 1
5
    
6
    while left <= right:
7
        pivot = (left + right) // 2
8
        if a[pivot] == x: 
9
            return pivot
10
        elif a[pivot] < x: 
11
            left = pivot + 1
12
        else: 
13
            right = pivot - 1
14
            
15
    return -1

(2) Searching Sorted Array: Binary Search (Recursion)

Time complexity $O(\log n)$.

xxxxxxxxxx
12
1
def re_binSearch(a, x, left, right):
2
  
3
    if left >= right: return -1
4
  
5
    pivot = (left + right) // 2
6
        
7
    if a[pivot] == x: 
8
       return pivot
9
    elif a[pivot] < x: 
10
       return re_binSearch(a, x, pivot + 1, right)
11
    else: 
12
       return re_binSearch(a, x, left, pivot - 1)

(3) Searching Hash Table

Time complexity at the best case is $O(1)$, and at the worst case is $O(n)$.

​x
1
def hashTable(a):
2
    buckets = [[] for i in range(len(a))]
3
    for x in a:
4
        idx = hash(x) % len(a)
5
        buckets[idx].append(x)
6
    return buckets
7
​
8
def hashSearch(a, x):
9
    ht = hashTable(a)
10
    for word in ht[hash(x) % len(a)]:
11
        if x == word:
12
            return True
13
    return False

(4) Search String Trie

String trie is a more efficient data structure for word searching. Suppose the trie nodes has,

xxxxxxxxxx
4
1
class TrieNode:
2
    def __init__(self):
3
        self.isword = False
4
        self.edges = {}

And we use the add function to add a new word to trie.

xxxxxxxxxx
10
1
def add(p:TrieNode, s:str, i=0) -> None:
2
  
3
    if i>=len(s):
4
        p.isword = True
5
        return
6
      
7
    if s[i] not in p.edges:
8
        p.edges[s[i]] = TrieNode()
9
        
10
    add(p.edges[s[i]], s, i+1)

Then, the following search algorithm (similar to walk through a graph) has a time complexity of $O(n)$ for searching a word in that data structure,

xxxxxxxxxx
14
1
def trieSearch(root:TrieNode, s:str, i=0) -> bool:
2
    
3
    p = root
4
    
5
    while p is not None:
6
      
7
        if i >= len(s): 
8
            return p.isword
9
          
10
        if s[i] not in p.edges: 
11
            return False
12
          
13
        p = p.edges[s[i]]
14
        i += 1