// v2 is O(n)

// v1 was O(n^2)

​

using System;

using System.Collections;

public class Program

{

    public static void Main()

    {

        Node root = new Node(1);

        root.left = new Node(2);

        root.right = new Node(3);

​

        //root.right.right = new Node(3);

        //root.right.right.right = new Node(3);

        //root.right.right.right.right = new Node(3);

        root.left.left = new Node(4);

        root.left.right = new Node(5);

​

        root.left.left.left = new Node(6);

        root.left.left.left.left = new Node(7);

        //root.left.left.left.left.left = new Node(8);

​

        Console.WriteLine(isBalanced(root));

    }

​

    public static bool isBalanced(Node n)

    {

        int o = Depth(n);

        if (o == -1)

            return false;

        return true;

    }

    public static int Depth(Node n)

    {

        if (n == null) return 0;

        int left = Depth(n.left);

        if (left == -1)

            return -1;

        int right = Depth(n.right);

        if (right == -1)

            return -1;

        if (Math.Abs(left-right) > 1)

        {

            return -1;

        }

        return 1 + Math.Max(left, right);

    }

    public class Node

    {

        public Node left = null;

        public Node right = null;

        public int data;

        public Node(int n)

        {

            this.data = n;

        }

    }

}