BreadthFirstTreeTraversal.cs

using System;
using System.Collections.Generic;
using DataStructures.BinarySearchTree;

namespace Algorithms.Graph
{
    /// <summary>
    ///     Breadth first tree traversal traverses through a binary tree
    ///     by iterating through each level first.
    ///     time complexity: O(n).
    ///     space complexity: O(w) where w is the max width of a binary tree.
    /// </summary>
    /// <typeparam name="TKey">Type of key held in binary search tree.</typeparam>
    public static class BreadthFirstTreeTraversal<TKey>
    {
        /// <summary>
        ///     Level Order Traversal returns an array of integers in order
        ///     of each level of a binary tree. It uses a queue to iterate
        ///     through each node following breadth first search traversal.
        /// </summary>
        /// <param name="tree">Passes the binary tree to traverse.</param>
        /// <returns>Returns level order traversal.</returns>
        public static TKey[] LevelOrderTraversal(BinarySearchTree<TKey> tree)
        {
            BinarySearchTreeNode<TKey>? root = tree.Root;
            TKey[] levelOrder = new TKey[tree.Count];
            if (root is null)
            {
                return Array.Empty<TKey>();
            }

            Queue<BinarySearchTreeNode<TKey>> breadthTraversal = new Queue<BinarySearchTreeNode<TKey>>();
            breadthTraversal.Enqueue(root);
            for (int i = 0; i < levelOrder.Length; i++)
            {
                BinarySearchTreeNode<TKey> current = breadthTraversal.Dequeue();
                levelOrder[i] = current.Key;
                if (current.Left is not null)
                {
                    breadthTraversal.Enqueue(current.Left);
                }

                if (current.Right is not null)
                {
                    breadthTraversal.Enqueue(current.Right);
                }
            }

            return levelOrder;
        }

        /// <summary>
        ///     Deepest Node return the deepest node in a binary tree. If more
        ///     than one node is on the deepest level, it is defined as the
        ///     right-most node of a binary tree. Deepest node uses breadth
        ///     first traversal to reach the end.
        /// </summary>
        /// <param name="tree">Tree passed to find deepest node.</param>
        /// <returns>Returns the deepest node in the tree.</returns>
        public static TKey? DeepestNode(BinarySearchTree<TKey> tree)
        {
            BinarySearchTreeNode<TKey>? root = tree.Root;
            if (root is null)
            {
                return default(TKey);
            }

            Queue<BinarySearchTreeNode<TKey>> breadthTraversal = new Queue<BinarySearchTreeNode<TKey>>();
            breadthTraversal.Enqueue(root);
            TKey deepest = root.Key;
            while (breadthTraversal.Count > 0)
            {
                BinarySearchTreeNode<TKey> current = breadthTraversal.Dequeue();
                if (current.Left is not null)
                {
                    breadthTraversal.Enqueue(current.Left);
                }

                if (current.Right is not null)
                {
                    breadthTraversal.Enqueue(current.Right);
                }

                deepest = current.Key;
            }

            return deepest;
        }
    }
}