Teaching Kids Programming – Using Double-Ended Queue to Perform a Breadth First Search Algorithm to Compute the Sum of the Nodes in a Binary Tree

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.

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.

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) —