Check if a binary tree is balance, i.e., all leaf nodes are on levels which difference does not exceed 1.

CheckTreeBalance.cs

// Deprecated in favor of https://github.com/puzzl3r/puzzles/tree/master/CheckTreeBalance

using System.Diagnostics;
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace ConsoleApplication8
{
    class Node
    {
        public Node L;
        public Node R;
    }

    class BalanceChecker
    {
        static void Main(string[] args)
        {
            // not balanced
            var r1 = new Node
            {
                L = new Node
                {
                    L = new Node
                    {
                        L = new Node
                        {
                            L = null,
                            R = null
                        },
                        R = null
                    },
                    R = null
                },
                R = new Node
                {
                    L = null,
                    R = null
                },
            };

            // balanced
            var r2 = new Node
            {
                L = new Node { L = null, R = null },
                R = new Node { L = null, R = new Node { L = null, R = null } }
            };

            // balanced
            var r3 = new Node { L = null, R = null };

            Debug.Assert(Check(r1) == false);
            Debug.Assert(Check(r2) == true);
            Debug.Assert(Check(r3) == true);
        }

        static public bool Check(Node r)
        {
            var h = new HashSet<int>();
            var s = new Stack<Node>();
            int d = 1;
            s.Push(null);
            s.Push(r);
            while (s.Count!=0)
            {
                var cur = s.Pop();
                if (cur==null)
                {
                    d--;
                }
                else if (cur.L==null && cur.R==null)
                {
                    Debug.Assert(h.Count <= 2);
                    if (h.Count<2)
                    {
                        h.Add(d);
                    }
                    else if (!h.Contains(d))
                    {
                        return false;
                    }
                    else
                    {
                        var a = h.ToArray();
                        if (Math.Abs(a[0] - a[1]) > 1) return false;
                    }
                }
                else
                {
                    s.Push(null);
                    d++;
                    if (cur.R != null) s.Push(cur.R);
                    if (cur.L != null) s.Push(cur.L);
                }
            }
            return true;
        }
    }
}