Teaching Kids Programming – Introduction to Trees, Binary Trees, Perfect Binary Trees, and BFS.

Teaching Kids Programming: Videos on Data Structures and Algorithms

Introduction to Trees and Binary Trees

A tree in math or data structure is upside-down. A tree has one root and all other nodes at 1 parent. The root does not have parent.

A binary tree is a tree that each node has at most two children nodes – in this case, we can name the children – left and right.

binary-tree

A perfect binary tree is a binary tree that all the interior nodes have two children and all the leaf nodes have the same depth/level.

vertical-binary-tree-order-2

If the depth of a perfect binary tree is D, we know the total number of nodes is pow(2, D) – 1

A Binary Search Tree is a binary tree that all the nodes have unique values and the left nodes are smaller than their parent nodes and the right nodes have larger values than their parent nodes.

Binary Search Tree

Introduction to Breadth First Search Algorithm

BFS or Breadth First Search is a traversal algorithm that visits the tree/graph in level by level order (Level-by-Level Tree Traversal). The python code looks like this:

1
2
3
4
5
6
7
8
9
10
11

def bfs(root):
  q = [] # queue
  q.append(root)
  while len(q) > 0:
     p = q[0]
     q.pop(0)  # dequeu
     print(p.val) # or do something with node p
     if p.left != None:
       q.append(p.left)
     if p.right != None:
       q.append(p.right)

def bfs(root):
  q = [] # queue
  q.append(root)
  while len(q) > 0:
     p = q[0]
     q.pop(0)  # dequeu
     print(p.val) # or do something with node p
     if p.left != None:
       q.append(p.left)
     if p.right != None:
       q.append(p.right)

–EOF (The Ultimate Computing & Technology Blog) —