15 Jun 2024•C++ / Python / TypeScript•Easy

Count Complete Tree Nodes

Collected C++, Python, TypeScript solutions for count complete tree nodes. Add a dedicated write-up later if you want deeper notes.

View original LeetCode question

auto-generated entry for Count Complete Tree Nodes. the solution files are available below.

solution files

C++ count-complete-tree-nodes/synced-solution.cpp
Python count-complete-tree-nodes/synced-solution.py
TypeScript count-complete-tree-nodes/synced-solution.ts

Solution files

Python•count-complete-tree-nodes/synced-solution.py

class Solution:
    def countNodes(self, root: Optional[TreeNode]) -> int:
        def left_height(node):
            height = class="syntax-number">0
            while node:
                height += class="syntax-number">1
                node = node.left
            return height

        def right_height(node):
            height = class="syntax-number">0
            while node:
                height += class="syntax-number">1
                node = node.right
            return height

        if not root:
            return class="syntax-number">0

        lh = left_height(root)
        rh = right_height(root)
        if lh == rh:
            return (class="syntax-number">1 << lh) - class="syntax-number">1
        return class="syntax-number">1 + self.countNodes(root.left) + self.countNodes(root.right)

C++•count-complete-tree-nodes/synced-solution.cpp

class Solution {
public:
    int countNodes(TreeNode* root) {
        if (!root) {
            return class="syntax-number">0;
        }

        int leftHeight = getLeftHeight(root);
        int rightHeight = getRightHeight(root);
        if (leftHeight == rightHeight) {
            return (class="syntax-number">1 << leftHeight) - class="syntax-number">1;
        }
        return class="syntax-number">1 + countNodes(root->left) + countNodes(root->right);
    }

private:
    int getLeftHeight(TreeNode* node) {
        int height = class="syntax-number">0;
        while (node) {
            height++;
            node = node->left;
        }
        return height;
    }

    int getRightHeight(TreeNode* node) {
        int height = class="syntax-number">0;
        while (node) {
            height++;
            node = node->right;
        }
        return height;
    }
};

TypeScript•count-complete-tree-nodes/synced-solution.ts

function countNodes(root: TreeNode | null): number {
    const getLeftHeight = (node: TreeNode | null): number => {
        let height = class="syntax-number">0;
        while (node) {
            height++;
            node = node.left;
        }
        return height;
    };

    const getRightHeight = (node: TreeNode | null): number => {
        let height = class="syntax-number">0;
        while (node) {
            height++;
            node = node.right;
        }
        return height;
    };

    if (!root) {
        return class="syntax-number">0;
    }

    const leftHeight = getLeftHeight(root);
    const rightHeight = getRightHeight(root);
    if (leftHeight === rightHeight) {
        return (class="syntax-number">1 << leftHeight) - class="syntax-number">1;
    }
    return class="syntax-number">1 + countNodes(root.left) + countNodes(root.right);
}