Tree Breadth First Search (BFS)

Binary Trees

As you might already know, the binary tree is a basic data structure in computer science that consists of nodes that point to each other. Each node can have a left child and/or a right child, or these can point to null i.e. they can have no children. The topmost node in the tree is called the root.

This week the problems focus on traversing a tree "level by level" i.e. by using a breadth first search (BFS). Although recursion is often the simplest way to traverse a tree structure for processing, it is actually simpler in this case to write this code using iteration.

We use a queue (a first-in, first-out list-like data structure) to do the following:

  • first add the root node of the tree to the queue
  • while the queue still has nodes in it, we should:
    • pop the next node

Problems for this Week

(easy) minimum-depth-of-binary-tree

Given a binary tree, find its minimum depth. The minimum depth is the number of nodes along the shortest path from the root node down to the nearest leaf node.

(medium) binary-tree-level-order-traversal

Given the rootof a binary tree, return the level order traversal of its nodes' values. (i.e., from left to right, level by level).

(medium) binary-tree-level-order-traversal-ii

Given the rootof a binary tree, return the bottom-up level order traversal of its nodes' values. (i.e., from left to right, level by level from leaf to root).

(medium) binary-tree-zigzag-level-order-traversal

Given the rootof a binary tree, return the zigzag level order traversal of its nodes' values. (i.e., from left to right, then right to left for the next level and alternate between).

(medium) populating-next-right-pointers-in-each-node

You are given a perfect binary tree where all leaves are on the same level, and every parent has two children. The binary tree has the following definition:

struct Node { int val; Node *left; Node *right; Node *next; }

Populate each next pointer to point to its next right node. If there is no next right node, the next pointer should be set to NULL. Initially, all next pointers are set to NULL.

note:** Grokking version assumes a non-perfect tree

(medium) binary-tree-right-side-view

Given the root of a binary tree, imagine yourself standing on the right side of it, return the values of the nodes you can see ordered from top to bottom.