Get Height of Binary Tree

Problem: Get the height of a binary tree.

Solution 1: Iterate

public class Node<T>
{
  public T Val;
  public Node<T> Left;
  public Node<T> Right;
}

public void GetHeight(Node  n)
{
  Queue q = new Queue<Node>();
  q.Enqueue(n);
  int height = 0;

  while (q.Any())
  {
    var countInLevel = q.Count;
    height++;

    while (countInLevel > 0)
    {
      var current = q.Dequeue();
      if (current.Left != null) q.Enqueue(current.Left);
      if (current.Right != null) q.Enqueue(current.Right);
      count--;
    }
  }

  return height;
}

Solution 2: Recursive

public class Node<T>
{
  public T Val;
  public Node<T> Left;
  public Node<T> Right;
}

public void GetHeight(Node  n)
{
  if (n == null) return  0;

  var left = GetHeight(n.Left);
  var right = GetHeight(n.Right);

  if (left > right){
    return left + 1;
  }
  else
  {
    return right + 1
  }
}

Leave a comment

Design a site like this with WordPress.com
Get started