Count Complete Tree Nodes

Leetcode Problem 222: Count Complete Tree Nodes

Problem Summary

Given the root of a complete binary tree, return the total number of nodes. In a complete binary tree, every level except possibly the last is fully filled, and all nodes in the last level are as far left as possible.

Design an algorithm that runs in less than O(n) time by exploiting the complete tree structure.

Constraints:

• The tree has between 0 and 50,000 nodes.
• Node values are non-negative integers up to 50,000.
• The tree is guaranteed to be complete.

Techniques

• Binary Search
• Bit Manipulation
• Tree
• Binary Tree

Solution

export class TreeNode {
    val: number
    left: TreeNode | null
    right: TreeNode | null

    constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
        this.val = (val === undefined ? 0 : val)
        this.left = (left === undefined ? null : left)
        this.right = (right === undefined ? null : right)
    }
}

function countNodes(root: TreeNode | null): number {
    if (!root) {
        return 0
    }

    let countLeft = countNodes(root.left)
    let countRight = countNodes(root.right)

    return 1 + countLeft + countRight
};