using System;

​

public class Program

{

    public static void Main()

    {

        /* 

                    A

            B               C

        D       E 

                    F

        */

        var nodeA = new Node();

        var nodeB = new Node();

        var nodeC = new Node();

        var nodeD = new Node();

        var nodeE = new Node();

        var nodeF = new Node();

        nodeA.Left = nodeB;

        nodeA.Right = nodeC;

        nodeB.Left = nodeD;

        nodeB.Right = nodeE;

        nodeE.Right = nodeF;

        Console.WriteLine("A tree IsBalanced: {0}", CheckIfBalanced(nodeA).IsBalanced);

        Console.WriteLine("B tree IsBalanced: {0}", CheckIfBalanced(nodeB).IsBalanced);

    }

​

    // Idea, you have to get to the bottom before being able to count.

    public static SubTreeInfo CheckIfBalanced(Node node)

    {

        SubTreeInfo leftSubTreeInfo = null;

        SubTreeInfo rightSubTreeInfo = null;

        var height = 1;

        if (node.Left != null)

        {

            leftSubTreeInfo = CheckIfBalanced(node.Left);

            height += leftSubTreeInfo.Height;

            // exit as soon you detect the tree is unbalanced

            if (!leftSubTreeInfo.IsBalanced)

            {

                return leftSubTreeInfo;

            }

        }

​

        if (node.Right != null)

        {

            rightSubTreeInfo = CheckIfBalanced(node.Right);

            height += rightSubTreeInfo.Height;

            // exit as soon you detect the tree is unbalanced

            if (!rightSubTreeInfo.IsBalanced)

            {

                return rightSubTreeInfo;

            }

        }

​

        var isBalanced = SubTreeInfo.GetDiffBetweenSubTrees(leftSubTreeInfo, rightSubTreeInfo) <= 1;

        return new SubTreeInfo(height, isBalanced);

    }

​

    public class SubTreeInfo

    {

        public int Height

        {

            get;

            set;

        }

​

        public bool IsBalanced

        {

            get;

            set;

        }

​

        public SubTreeInfo(int height, bool isBalanced)

        {

            Height = height;

            IsBalanced = isBalanced;

        }

​

        public static int GetDiffBetweenSubTrees(SubTreeInfo left, SubTreeInfo right)

        {

            var leftHeight = 0;

            var rightHeight = 0;

            if (left != null)

            {

                leftHeight = left.Height;

            }

​

            if (right != null)

            {

                rightHeight = right.Height;

            }

​

            return Math.Abs(leftHeight - rightHeight);

        }

    }

​

    public class Node

    {

        public Node Left

        {

            get;

            set;

        }

​

        public Node Right

        {

            get;

            set;

        }

    }

}