struct Node
{
    int Data;
    Node *Left, *Right;

    Node(int data, Node *left = NULL, Node *right = NULL) : Data(data), Left(left), Right(right) {}
};

class Solution
{
public:
    int GetWidth(Node *root)
    {
        _heightMem.clear();

        return GetWidthHelper(root);
    }

private:
    unordered_map<Node *, int> _heightMem;



    int GetHeight(Node *root)
    {
        if (root == NULL)
            return 0;

        auto findRes = _heightMem.find(root);
        if (findRes != _heightMem.end())
            return findRes->second;

        int res = max(GetHeight(root->Left), GetHeight(root->Right)) + 1;
        _heightMem[root] = res;

        return res;
    }

    int GetWidthHelper(Node *root)
    {
        if (root == NULL)
            return 0;

        int leftWidth = GetWidthHelper(root->Left);
        int rightWidth = GetWidthHelper(root->Right);
        int rootWidth = GetHeight(root->Left) + GetHeight(root->Right) + 1;

        return max(max(leftWidth, rightWidth), rootWidth);
    }
};



int _tmain(int argc, _TCHAR* argv[])
{
    Node node3 = Node(3);
    Node node2 = Node(2, &node3, NULL);
    Node node4 = Node(4);
    Node node1 = Node(1, &node2, &node4);

    Solution s;

    assert(s.GetWidth(NULL) == 0);
    assert(s.GetWidth(&node1) == 4);

    return 0;
}