Binary search tree level by level average
We need to use a for loop with BFS to solve this problem.
class Program
{
public class Solution
{
static void Main()
{
MyBST bst = new MyBST();
bst.InsertNode(11);
bst.InsertNode(9);
bst.InsertNode(12);
bst.InsertNode(8);
bst.InsertNode(10);
bst.printTree(bst.head);
Console.WriteLine("____");
IList<double> ans = bst.AverageOfLevels(bst.head);
foreach (double num in ans)
Console.WriteLine(num);
}
public class MyBST
{
public TreeNode head { get; set; }
public class TreeNode
{
public int val;
public TreeNode left;
public TreeNode right;
public TreeNode(int val = 0, TreeNode left = null, TreeNode right = null)
{
this.val = val;
this.left = left;
this.right = right;
}
}
public void InsertNode(int x)
{
insert(x, head);
}
public void insert(int x, TreeNode root)
{
if (root == null)
{
TreeNode n = new TreeNode(x, null, null);
root = n;
head = n;
}
else
{
if (x < root.val)
{
if (root.left == null)
{
TreeNode n = new TreeNode(x, null, null);
root.left = n;
}
else
insert(x, root.left);
}
else if (x > root.val)
{
if (root.right == null)
{
TreeNode n = new TreeNode(x, null, null);
root.right = n;
}
else
insert(x, root.right);
}
}
}
public IList<double> AverageOfLevels(TreeNode root)
{
Queue<TreeNode> q = new Queue<TreeNode>();
IList<double> list = new List<double>();
if (root != null)
{
q.Enqueue(root);
while (q.Count != 0)
{
int c = q.Count;
double sum = 0;
for (int i = 0; i < c; i++)
{
TreeNode curRoot = q.Dequeue();
if (curRoot != null)
{
sum += curRoot.val;
}
if (curRoot.left != null)
q.Enqueue(curRoot.left);
if (curRoot.right != null)
q.Enqueue(curRoot.right);
}
list.Add(sum / c);
}
}
return list;
}
public void printTree(TreeNode root)
{
Queue<TreeNode> queue = new Queue<TreeNode>();
queue.Enqueue(root);
while (!(queue.Count == 0))
{
TreeNode node = queue.Peek();
if (node != null)
{
Console.WriteLine(node.val + " ");
queue.Dequeue();
if (node.left != null)
queue.Enqueue(node.left);
if (node.right != null)
queue.Enqueue(node.right);
}
}
}
}
}
}