Breadth First Search

Breadth-First Search (BFS) is a graph traversal algorithm used to explore and search through data structures like graphs or trees. It starts at a given node (usually the root node) and explores all its neighbors at the present depth before moving on to nodes at the next depth level. In essence, BFS explores nodes level by level, moving outward from the starting point.

• 1.1) Binary Tree Level Order Traversal
  Given the root of a binary tree, return the level order traversal of its nodes’ values. Level order traversal means visiting all nodes at each level from left to right before moving on to the next level.
• 1.2) Binary Tree Level Order Traversal II
  Given the root of a binary tree, return the bottom-up level order traversal of its nodes’ values. The bottom-up level order traversal means visiting all nodes at each level from left to right before moving on to the next level, and then returning the result in reverse order (from bottom to top).
• 1.3) Binary Tree Zigzag Level Order Traversal
  Given the root of a binary tree, return the zigzag level order traversal of its nodes’ values. Zigzag level order traversal means visiting all nodes at each level alternatively from left to right and right to left.
• 2.6) Average of Levels in Binary Tree
  Given the root of a binary tree, return the average value of the nodes on each level of the tree.