Trees Height

The height of a tree is defined to be the maximum distance from the root node to any leaf node. Write a function to calculate the height of an arbitrary tree. Since the height of a tree equals to the height of its tallest subtree plus one, we can write a recursive function like this

//Data structure to a store a binary tree node
public class Node
{
	public Node? Left { get; set; } = null;
	public Node? Right { get; set; } = null;
	public int Value { get; }
	public Node(int value, Node? left = null, Node? right = null)
	{
		Left = left;
		Right = right;
		Value = value;
	}
}

/// <summary>
/// Reursively find a tree height
/// </summary>
/// <param name="root">root node</param>
/// <returns></returns>
public static int TreeHeightRecursive(Node? root)
{
	if (root == null) return 0;
	return 1 + Math.Max(
		TreeHeightRecursive(root.Left),
		TreeHeightRecursive(root.Right)
	);
}

/// <summary>
/// Iteratively find a tree's height
/// </summary>
/// <param name="root">root node</param>
/// <returns></returns>
public static int TreeHeightIterative(Node root)
{
	//special case 
	if (root == null) return 0;

	//create a queue to store the nodes
	System.Collections.Generic.Queue<Node> q = new();
	q.Enqueue(root);
	int height = 0;
	Node? top = null;

	while (q.Count != 0)
	{
		//caculate the total # of nodes at the current level
		int count = q.Count;

		//process each node and enequeue their left and right child
		for(int i = 0; i < count; i++)
		{
			if (q.TryPeek(out _))
			{
				top = q.Dequeue();
				if (top.Left != null)
					q.Enqueue(top.Left);

				if (top.Right != null)
					q.Enqueue(top.Right);
			}
		}
		height++;   
	}
	return height;
}

Running time is O(n) since it is called for each child of each node.