from typing import Optional
 
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
 
class Solution:
    def countNodes(self, root: Optional[TreeNode]) -> int:
        if not root: return 0
        def maxDepth(root):
            # this finds the maximum depth of the tree 
            # it goes down just the left side of the tree, where nodes are guaranteed
            # O(d) - depth of left-side
            if not root:
                return -1
 
            return 1 + maxDepth(root.left)
 
 
        d = maxDepth(root)
        def dfs(root, depth):
            if not root:
                return 0
            if depth == d:
                # if we've reached the bottom nodes, return 1 (counting itself)
                return 1
 
            left, right, mid = 0, 0, (2 ** (d - depth)) // 2
            left = dfs(root.left, depth + 1)
            if left < mid:
                # determine if we must go to the right (halve the problem)
                # depends on how many bottom nodes are returned by the left recursion
                # for instance, if the depth of the tree is 4 (start from 0), and 
                # the current depth is 2, then this subtree should have 4 bottom nodes
                # if it doesn't, the parent does not have to recurse rightward
                right = dfs(root.right, depth + 1)
 
            return mid + right
 
        bottom = dfs(root, 0)
        top = (2 ** (d)) - 1
        return top + bottom
 
def make_node(): return TreeNode(None, None, None)
tree = make_node()
tree.left = make_node()
tree.right = make_node()
tree.left.left = make_node()
 
print(Solution().countNodes(tree))

ZnJvbSB0eXBpbmcgaW1wb3J0IE9wdGlvbmFsCgpjbGFzcyBUcmVlTm9kZToKICAgIGRlZiBfX2luaXRfXyhzZWxmLCB2YWw9MCwgbGVmdD1Ob25lLCByaWdodD1Ob25lKToKICAgICAgICBzZWxmLnZhbCA9IHZhbAogICAgICAgIHNlbGYubGVmdCA9IGxlZnQKICAgICAgICBzZWxmLnJpZ2h0ID0gcmlnaHQKCmNsYXNzIFNvbHV0aW9uOgogICAgZGVmIGNvdW50Tm9kZXMoc2VsZiwgcm9vdDogT3B0aW9uYWxbVHJlZU5vZGVdKSAtPiBpbnQ6CiAgICAgICAgaWYgbm90IHJvb3Q6IHJldHVybiAwCiAgICAgICAgZGVmIG1heERlcHRoKHJvb3QpOgogICAgICAgICAgICAjIHRoaXMgZmluZHMgdGhlIG1heGltdW0gZGVwdGggb2YgdGhlIHRyZWUgCiAgICAgICAgICAgICMgaXQgZ29lcyBkb3duIGp1c3QgdGhlIGxlZnQgc2lkZSBvZiB0aGUgdHJlZSwgd2hlcmUgbm9kZXMgYXJlIGd1YXJhbnRlZWQKICAgICAgICAgICAgIyBPKGQpIC0gZGVwdGggb2YgbGVmdC1zaWRlCiAgICAgICAgICAgIGlmIG5vdCByb290OgogICAgICAgICAgICAgICAgcmV0dXJuIC0xCgogICAgICAgICAgICByZXR1cm4gMSArIG1heERlcHRoKHJvb3QubGVmdCkKICAgICAgICAKCiAgICAgICAgZCA9IG1heERlcHRoKHJvb3QpCiAgICAgICAgZGVmIGRmcyhyb290LCBkZXB0aCk6CiAgICAgICAgICAgIGlmIG5vdCByb290OgogICAgICAgICAgICAgICAgcmV0dXJuIDAKICAgICAgICAgICAgaWYgZGVwdGggPT0gZDoKICAgICAgICAgICAgICAgICMgaWYgd2UndmUgcmVhY2hlZCB0aGUgYm90dG9tIG5vZGVzLCByZXR1cm4gMSAoY291bnRpbmcgaXRzZWxmKQogICAgICAgICAgICAgICAgcmV0dXJuIDEKICAgICAgICAgICAgCiAgICAgICAgICAgIGxlZnQsIHJpZ2h0LCBtaWQgPSAwLCAwLCAoMiAqKiAoZCAtIGRlcHRoKSkgLy8gMgogICAgICAgICAgICBsZWZ0ID0gZGZzKHJvb3QubGVmdCwgZGVwdGggKyAxKQogICAgICAgICAgICBpZiBsZWZ0IDwgbWlkOgogICAgICAgICAgICAgICAgIyBkZXRlcm1pbmUgaWYgd2UgbXVzdCBnbyB0byB0aGUgcmlnaHQgKGhhbHZlIHRoZSBwcm9ibGVtKQogICAgICAgICAgICAgICAgIyBkZXBlbmRzIG9uIGhvdyBtYW55IGJvdHRvbSBub2RlcyBhcmUgcmV0dXJuZWQgYnkgdGhlIGxlZnQgcmVjdXJzaW9uCiAgICAgICAgICAgICAgICAjIGZvciBpbnN0YW5jZSwgaWYgdGhlIGRlcHRoIG9mIHRoZSB0cmVlIGlzIDQgKHN0YXJ0IGZyb20gMCksIGFuZCAKICAgICAgICAgICAgICAgICMgdGhlIGN1cnJlbnQgZGVwdGggaXMgMiwgdGhlbiB0aGlzIHN1YnRyZWUgc2hvdWxkIGhhdmUgNCBib3R0b20gbm9kZXMKICAgICAgICAgICAgICAgICMgaWYgaXQgZG9lc24ndCwgdGhlIHBhcmVudCBkb2VzIG5vdCBoYXZlIHRvIHJlY3Vyc2UgcmlnaHR3YXJkCiAgICAgICAgICAgICAgICByaWdodCA9IGRmcyhyb290LnJpZ2h0LCBkZXB0aCArIDEpCiAgICAgICAgICAgIAogICAgICAgICAgICByZXR1cm4gbWlkICsgcmlnaHQKCiAgICAgICAgYm90dG9tID0gZGZzKHJvb3QsIDApCiAgICAgICAgdG9wID0gKDIgKiogKGQpKSAtIDEKICAgICAgICByZXR1cm4gdG9wICsgYm90dG9tCgpkZWYgbWFrZV9ub2RlKCk6IHJldHVybiBUcmVlTm9kZShOb25lLCBOb25lLCBOb25lKQp0cmVlID0gbWFrZV9ub2RlKCkKdHJlZS5sZWZ0ID0gbWFrZV9ub2RlKCkKdHJlZS5yaWdodCA9IG1ha2Vfbm9kZSgpCnRyZWUubGVmdC5sZWZ0ID0gbWFrZV9ub2RlKCkKCnByaW50KFNvbHV0aW9uKCkuY291bnROb2Rlcyh0cmVlKSk=