Teaching Kids Programming: Videos on Data Structures and Algorithms
Introduction to Data Structure Double-Ended Queue
So far, we have learned the Queue (First In First Out) and Priority Queue (First In Priority Out). A Double-ended queue e.g. deque is just like a normal queue but if also offers ability to enqueue from the front and deque from the rear.
1 2 3 4 5 6 7 8 9 10 | from collections import deque q = deque() q.append(1) # [1] q.append(2) # [1, 2] q.append(3) # [1, 2, 3] q.appendleft(4) # [4, 1, 2, 3] q.appendleft(5) # [5, 4, 1, 2, 3] x = q.pop() # x = 3, q = [5, 4, 1, 2] x = q.popleft() # x = 5, q = [4, 1, 2] |
from collections import deque q = deque() q.append(1) # [1] q.append(2) # [1, 2] q.append(3) # [1, 2, 3] q.appendleft(4) # [4, 1, 2, 3] q.appendleft(5) # [5, 4, 1, 2, 3] x = q.pop() # x = 3, q = [5, 4, 1, 2] x = q.popleft() # x = 5, q = [4, 1, 2]
If we are popping one element (deque) using a list via q.pop(0), the complexity worst time is O(N), but using deque makes sure the deque/enque is always O(1) constant.
Compute the Sum of the Nodes in a Binary Tree using Breadth First Search Algorithm
A queue is the data structure to use when we perform a Breadth First Search (BFS) Algorithm. We can compute the nodes sum by using queue to traverse the tree level-by-level.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 | from collections import deque def sumOfTree(root): if root is None: return 0 q = deque() q.append(root) ans = 0 while len(q) > 0: p = q.popleft() ans += p.val if p.left: q.append(p.left) if p.right: q.append(p.right) return ans class Node: def __init__(self, val, left=None, right=None): self.val = val self.left = left self.right = right def addLeftChild(self, val): newNode = Node(val) self.left = newNode return newNode def addRightChild(self, val): newNode = Node(val) self.right = newNode return newNode # 1 # / \ # 2 3 # / \ # 4 5 root = Node(1) root.addLeftChild(2) right = root.addRightChild(3) right.addLeftChild(4) right.addRightChild(5) print(sumOfTree(root)) # 15 |
from collections import deque
def sumOfTree(root):
if root is None:
return 0
q = deque()
q.append(root)
ans = 0
while len(q) > 0:
p = q.popleft()
ans += p.val
if p.left:
q.append(p.left)
if p.right:
q.append(p.right)
return ans
class Node:
def __init__(self, val, left=None, right=None):
self.val = val
self.left = left
self.right = right
def addLeftChild(self, val):
newNode = Node(val)
self.left = newNode
return newNode
def addRightChild(self, val):
newNode = Node(val)
self.right = newNode
return newNode
# 1
# / \
# 2 3
# / \
# 4 5
root = Node(1)
root.addLeftChild(2)
right = root.addRightChild(3)
right.addLeftChild(4)
right.addRightChild(5)
print(sumOfTree(root)) # 15–EOF (The Ultimate Computing & Technology Blog) —
GD Star Rating
loading...
398 wordsloading...
Last Post: The art of creating or sourcing quality and compelling content on Instagram
Next Post: Recursion and Two Pointer Algorithms to Determine Four Sum
