Count Complete Tree Nodes

Problem Statement

Given the root of a complete binary tree, return the number of the nodes in the tree.

A complete binary tree is a binary tree in which every level, except possibly the last, is completely filled, and all nodes in the last level are as far left as possible.

What to notice first

• Complete tree property: last level filled left-to-right, all other levels complete.
• If left subtree height == right subtree height, left is perfect: count = 2^(h+1) - 1.
• Otherwise, right is perfect: count = 2^h - 1.
• Both approaches exploit this property to achieve O(log² n).

Examples

Input	Output	Explanation
[1,2,3,4,5,6]	6	All 6 nodes present in complete tree
[1,2,3,4,5,6,7]	7	Perfect binary tree of height 2

Constraints

• The number of nodes is in the range [1, 5 * 10^4].
• 0 <= Node.val <= 100

Real-World Applications

Where this pattern appears

• File system hierarchies and directory structures
• DOM tree manipulation in web browsers
• XML/JSON parsing and configuration management
• Organizational hierarchies and permission trees

Complexity Comparison

Approach	Time	Space	Best When
Level Calculation	O(log² n)	O(log n)	Direct height comparison intuitive
Binary Search	O(log² n)	O(log n)	Explicit search on position space

Approach 1: Level Calculation

★ Recommended

Calculate left and right subtree heights. If equal, left is perfect; otherwise, right is perfect. Use formula 2^h - 1 for perfect subtrees.

⏱ Time O(log² n) Recursive depth × height calculation 💾 Space O(log n) Recursion stack

Pseudocode

function countNodes(root):
    if not root: return 0

    leftHeight = countLeftDepth(root)
    rightHeight = countRightDepth(root)

    if leftHeight == rightHeight:
        return (2^(leftHeight+1) - 1) + countNodes(root.right)
    else:
        return (2^(rightHeight+1) - 1) + countNodes(root.left)

Solution Code

Python

count_complete_tree_nodes_level_calculation.py

from typing import Optional


# Definition for a binary tree node.
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right


def countNodes(root: Optional[TreeNode]) -> int:
    """
    Count nodes in complete binary tree using level calculation.
    For complete tree, if left height == right height, left is perfect.
    Time: O(log² n), Space: O(log n) for recursion
    """
    if not root:
        return 0

    # Calculate left and right heights
    left_height = 0
    left_node = root.left
    while left_node:
        left_height += 1
        left_node = left_node.left

    right_height = 0
    right_node = root.right
    while right_node:
        right_height += 1
        right_node = right_node.right

    if left_height == right_height:
        # Left subtree is perfect: 2^h - 1 nodes + root + recursively count right
        return (1 << (left_height + 1)) - 1 + countNodes(root.right)
    else:
        # Right subtree is perfect: 2^h - 1 nodes + root + recursively count left
        return (1 << (right_height + 1)) - 1 + countNodes(root.left)


# Test cases
if __name__ == "__main__":
    # Example 1: Complete tree with 5 nodes
    root = TreeNode(1)
    root.left = TreeNode(2)
    root.right = TreeNode(3)
    root.left.left = TreeNode(4)
    root.left.right = TreeNode(5)

    print(f"Example 1 node count: {countNodes(root)}")  # 5

    # Example 2: Single node
    single = TreeNode(1)
    print(f"Example 2 node count: {countNodes(single)}")  # 1

    # Example 3: Empty tree
    print(f"Example 3 node count: {countNodes(None)}")  # 0

C++

count_complete_tree_nodes_level_calculation.cpp

#include <iostream>
using namespace std;

// Definition for a binary tree node.
struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

class Solution {
public:
    int countNodes(TreeNode* root) {
        /**
         * Count nodes in complete binary tree using level calculation.
         * For complete tree, if left height == right height, left is perfect.
         * Time: O(log² n), Space: O(log n) for recursion
         */
        if (!root) return 0;

        // Calculate left and right heights
        int left_height = 0;
        TreeNode* left_node = root->left;
        while (left_node) {
            left_height++;
            left_node = left_node->left;
        }

        int right_height = 0;
        TreeNode* right_node = root->right;
        while (right_node) {
            right_height++;
            right_node = right_node->right;
        }

        if (left_height == right_height) {
            // Left subtree is perfect: 2^(h+1) - 1 nodes + root + recursively count right
            return (1 << (left_height + 1)) - 1 + countNodes(root->right);
        } else {
            // Right subtree is perfect: 2^h - 1 nodes + root + recursively count left
            return (1 << (right_height + 1)) - 1 + countNodes(root->left);
        }
    }
};

// Test cases
int main() {
    // Example 1: Complete tree with 5 nodes
    TreeNode* root = new TreeNode(1);
    root->left = new TreeNode(2);
    root->right = new TreeNode(3);
    root->left->left = new TreeNode(4);
    root->left->right = new TreeNode(5);

    Solution sol;
    cout << "Example 1 node count: " << sol.countNodes(root) << endl;  // 5

    // Example 2: Single node
    TreeNode* single = new TreeNode(1);
    cout << "Example 2 node count: " << sol.countNodes(single) << endl;  // 1

    // Example 3: Empty tree
    cout << "Example 3 node count: " << sol.countNodes(nullptr) << endl;  // 0

    return 0;
}

Java

CountCompleteTreeNodesLevelCalculation.java

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode() {}
    TreeNode(int val) {
        this.val = val;
    }
}

class Solution {
    /**
     * Count nodes in complete binary tree using level calculation.
     * For complete tree, if left height == right height, left is perfect.
     * Time: O(log² n), Space: O(log n) for recursion
     */
    public int countNodes(TreeNode root) {
        if (root == null) return 0;

        // Calculate left and right heights
        int leftHeight = 0;
        TreeNode leftNode = root.left;
        while (leftNode != null) {
            leftHeight++;
            leftNode = leftNode.left;
        }

        int rightHeight = 0;
        TreeNode rightNode = root.right;
        while (rightNode != null) {
            rightHeight++;
            rightNode = rightNode.right;
        }

        if (leftHeight == rightHeight) {
            // Left subtree is perfect: 2^(h+1) - 1 nodes + root + recursively count right
            return (1 << (leftHeight + 1)) - 1 + countNodes(root.right);
        } else {
            // Right subtree is perfect: 2^h - 1 nodes + root + recursively count left
            return (1 << (rightHeight + 1)) - 1 + countNodes(root.left);
        }
    }
}

class Main {
    public static void main(String[] args) {
        // Example 1: Complete tree with 5 nodes
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(2);
        root.right = new TreeNode(3);
        root.left.left = new TreeNode(4);
        root.left.right = new TreeNode(5);

        Solution sol = new Solution();
        System.out.println("Example 1 node count: " + sol.countNodes(root));  // 5

        // Example 2: Single node
        TreeNode single = new TreeNode(1);
        System.out.println("Example 2 node count: " + sol.countNodes(single));  // 1

        // Example 3: Empty tree
        System.out.println("Example 3 node count: " + sol.countNodes(null));  // 0
    }
}

JavaScript

count_complete_tree_nodes_level_calculation.js

/**
 * Definition for a binary tree node.
 */
class TreeNode {
    constructor(val = 0, left = null, right = null) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

/**
 * Count nodes in complete binary tree using level calculation.
 * For complete tree, if left height == right height, left is perfect.
 * Time: O(log² n), Space: O(log n) for recursion
 * @param {TreeNode} root
 * @return {number}
 */
function countNodes(root) {
    if (!root) return 0;

    // Calculate left and right heights
    let leftHeight = 0;
    let leftNode = root.left;
    while (leftNode) {
        leftHeight++;
        leftNode = leftNode.left;
    }

    let rightHeight = 0;
    let rightNode = root.right;
    while (rightNode) {
        rightHeight++;
        rightNode = rightNode.right;
    }

    if (leftHeight === rightHeight) {
        // Left subtree is perfect: 2^(h+1) - 1 nodes + root + recursively count right
        return (1 << (leftHeight + 1)) - 1 + countNodes(root.right);
    } else {
        // Right subtree is perfect: 2^h - 1 nodes + root + recursively count left
        return (1 << (rightHeight + 1)) - 1 + countNodes(root.left);
    }
}

// Test cases
const root1 = new TreeNode(1);
root1.left = new TreeNode(2);
root1.right = new TreeNode(3);
root1.left.left = new TreeNode(4);
root1.left.right = new TreeNode(5);

console.log("Example 1 node count:", countNodes(root1));  // 5

const single = new TreeNode(1);
console.log("Example 2 node count:", countNodes(single));  // 1

console.log("Example 3 node count:", countNodes(null));  // 0

Rust

count_complete_tree_nodes_level_calculation.rs

use std::cell::RefCell;
use std::rc::Rc;

#[derive(Debug)]
pub struct TreeNode {
    pub val: i32,
    pub left: Option<Rc<RefCell<TreeNode>>>,
    pub right: Option<Rc<RefCell<TreeNode>>>,
}

impl TreeNode {
    pub fn new(val: i32) -> Self {
        TreeNode {
            val,
            left: None,
            right: None,
        }
    }
}

/**
 * Count nodes in complete binary tree using level calculation.
 * For complete tree, if left height == right height, left is perfect.
 * Time: O(log² n), Space: O(log n) for recursion
 */
pub fn count_nodes(root: Option<Rc<RefCell<TreeNode>>>) -> i32 {
    match root {
        None => 0,
        Some(node) => {
            let node_ref = node.borrow();

            // Calculate left and right heights
            let mut left_height = 0;
            let mut left_node = node_ref.left.clone();
            while let Some(n) = left_node.clone() {
                left_height += 1;
                let n_ref = n.borrow();
                left_node = n_ref.left.clone();
            }

            let mut right_height = 0;
            let mut right_node = node_ref.right.clone();
            while let Some(n) = right_node.clone() {
                right_height += 1;
                let n_ref = n.borrow();
                right_node = n_ref.right.clone();
            }

            let right = node_ref.right.clone();
            let left = node_ref.left.clone();
            drop(node_ref);

            if left_height == right_height {
                // Left subtree is perfect: 2^(h+1) - 1 nodes + root + recursively count right
                ((1 << (left_height + 1)) - 1) + count_nodes(right)
            } else {
                // Right subtree is perfect: 2^h - 1 nodes + root + recursively count left
                ((1 << (right_height + 1)) - 1) + count_nodes(left)
            }
        }
    }
}

fn main() {
    println!("Example 1: Count complete tree nodes with level calculation");
}

Go

count_complete_tree_nodes_level_calculation.go

package main

import "fmt"

/**
 * Definition for a binary tree node.
 */
type TreeNode struct {
    Val   int
    Left  *TreeNode
    Right *TreeNode
}

/**
 * Count nodes in complete binary tree using level calculation.
 * For complete tree, if left height == right height, left is perfect.
 * Time: O(log² n), Space: O(log n) for recursion
 */
func countNodes(root *TreeNode) int {
    if root == nil {
        return 0
    }

    // Calculate left and right heights
    leftHeight := 0
    leftNode := root.Left
    for leftNode != nil {
        leftHeight++
        leftNode = leftNode.Left
    }

    rightHeight := 0
    rightNode := root.Right
    for rightNode != nil {
        rightHeight++
        rightNode = rightNode.Right
    }

    if leftHeight == rightHeight {
        // Left subtree is perfect: 2^(h+1) - 1 nodes + root + recursively count right
        return (1 << (leftHeight + 1)) - 1 + countNodes(root.Right)
    } else {
        // Right subtree is perfect: 2^h - 1 nodes + root + recursively count left
        return (1 << (rightHeight + 1)) - 1 + countNodes(root.Left)
    }
}

func main() {
    fmt.Println("Example 1: Count complete tree nodes with level calculation")
}

Approach 2: Binary Search on Positions

alternative

For complete tree of height h, search for the last node position. Use existence check to binary search the position space [2^(h-1), 2^h - 1].

⏱ Time O(log² n) Binary search × traversal to position 💾 Space O(log n) Recursion stack

Solution Code

Python

count_complete_tree_nodes_binary_search.py

from typing import Optional


# Definition for a binary tree node.
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right


def countNodes(root: Optional[TreeNode]) -> int:
    """
    Count nodes in complete binary tree using binary search on node positions.
    Uses existence check for node at each possible position.
    Time: O(log² n), Space: O(log n) for recursion
    """
    if not root:
        return 0

    # Find height of tree
    height = 0
    node = root
    while node:
        height += 1
        node = node.left

    # Binary search on number of nodes
    # For a complete tree of height h, nodes range from 2^(h-1) to 2^h - 1
    low = 1 << (height - 1)  # 2^(h-1)
    high = (1 << height) - 1  # 2^h - 1

    def exists(pos, height, root):
        """Check if node at position pos exists (0-indexed, 1-based actual position)."""
        left, right = 0, (1 << (height - 1)) - 1

        for _ in range(height - 1):
            mid = (left + right + 1) // 2
            if pos >= mid:
                root = root.right
                left = mid
            else:
                root = root.left
                right = mid - 1

        return root is not None

    while low <= high:
        mid = (low + high + 1) // 2
        if exists(mid, height, root):
            low = mid
        else:
            high = mid - 1

    return low


# Test cases
if __name__ == "__main__":
    # Example 1: Complete tree with 5 nodes
    root = TreeNode(1)
    root.left = TreeNode(2)
    root.right = TreeNode(3)
    root.left.left = TreeNode(4)
    root.left.right = TreeNode(5)

    print(f"Example 1 node count: {countNodes(root)}")  # 5

    # Example 2: Single node
    single = TreeNode(1)
    print(f"Example 2 node count: {countNodes(single)}")  # 1

    # Example 3: Empty tree
    print(f"Example 3 node count: {countNodes(None)}")  # 0

C++

count_complete_tree_nodes_binary_search.cpp

#include <iostream>
using namespace std;

// Definition for a binary tree node.
struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

class Solution {
private:
    bool exists(long long pos, int height, TreeNode* root) {
        /**Check if node at position pos exists (0-indexed, 1-based actual position).*/
        long long left = 0, right = (1LL << (height - 1)) - 1;

        for (int i = 0; i < height - 1; i++) {
            long long mid = (left + right + 1) / 2;
            if (pos >= mid) {
                root = root->right;
                left = mid;
            } else {
                root = root->left;
                right = mid - 1;
            }
        }

        return root != nullptr;
    }

public:
    int countNodes(TreeNode* root) {
        /**
         * Count nodes in complete binary tree using binary search on node positions.
         * Uses existence check for node at each possible position.
         * Time: O(log² n), Space: O(log n) for recursion
         */
        if (!root) return 0;

        // Find height of tree
        int height = 0;
        TreeNode* node = root;
        while (node) {
            height++;
            node = node->left;
        }

        // Binary search on number of nodes
        // For a complete tree of height h, nodes range from 2^(h-1) to 2^h - 1
        long long low = 1LL << (height - 1);   // 2^(h-1)
        long long high = (1LL << height) - 1;  // 2^h - 1

        while (low <= high) {
            long long mid = (low + high + 1) / 2;
            if (exists(mid, height, root)) {
                low = mid;
            } else {
                high = mid - 1;
            }
        }

        return (int)low;
    }
};

// Test cases
int main() {
    // Example 1: Complete tree with 5 nodes
    TreeNode* root = new TreeNode(1);
    root->left = new TreeNode(2);
    root->right = new TreeNode(3);
    root->left->left = new TreeNode(4);
    root->left->right = new TreeNode(5);

    Solution sol;
    cout << "Example 1 node count: " << sol.countNodes(root) << endl;  // 5

    // Example 2: Single node
    TreeNode* single = new TreeNode(1);
    cout << "Example 2 node count: " << sol.countNodes(single) << endl;  // 1

    // Example 3: Empty tree
    cout << "Example 3 node count: " << sol.countNodes(nullptr) << endl;  // 0

    return 0;
}

Java

CountCompleteTreeNodesBinarySearch.java

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode() {}
    TreeNode(int val) {
        this.val = val;
    }
}

class Solution {
    private boolean exists(long pos, int height, TreeNode root) {
        /**Check if node at position pos exists.*/
        long left = 0, right = (1L << (height - 1)) - 1;

        for (int i = 0; i < height - 1; i++) {
            long mid = (left + right + 1) / 2;
            if (pos >= mid) {
                root = root.right;
                left = mid;
            } else {
                root = root.left;
                right = mid - 1;
            }
        }

        return root != null;
    }

    /**
     * Count nodes in complete binary tree using binary search on node positions.
     * Uses existence check for node at each possible position.
     * Time: O(log² n), Space: O(log n) for recursion
     */
    public int countNodes(TreeNode root) {
        if (root == null) return 0;

        // Find height of tree
        int height = 0;
        TreeNode node = root;
        while (node != null) {
            height++;
            node = node.left;
        }

        // Binary search on number of nodes
        // For a complete tree of height h, nodes range from 2^(h-1) to 2^h - 1
        long low = 1L << (height - 1);   // 2^(h-1)
        long high = (1L << height) - 1;  // 2^h - 1

        while (low <= high) {
            long mid = (low + high + 1) / 2;
            if (exists(mid, height, root)) {
                low = mid;
            } else {
                high = mid - 1;
            }
        }

        return (int)low;
    }
}

class Main {
    public static void main(String[] args) {
        // Example 1: Complete tree with 5 nodes
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(2);
        root.right = new TreeNode(3);
        root.left.left = new TreeNode(4);
        root.left.right = new TreeNode(5);

        Solution sol = new Solution();
        System.out.println("Example 1 node count: " + sol.countNodes(root));  // 5

        // Example 2: Single node
        TreeNode single = new TreeNode(1);
        System.out.println("Example 2 node count: " + sol.countNodes(single));  // 1

        // Example 3: Empty tree
        System.out.println("Example 3 node count: " + sol.countNodes(null));  // 0
    }
}

JavaScript

count_complete_tree_nodes_binary_search.js

/**
 * Definition for a binary tree node.
 */
class TreeNode {
    constructor(val = 0, left = null, right = null) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

/**
 * Count nodes in complete binary tree using binary search on node positions.
 * Uses existence check for node at each possible position.
 * Time: O(log² n), Space: O(log n) for recursion
 * @param {TreeNode} root
 * @return {number}
 */
function countNodes(root) {
    if (!root) return 0;

    function exists(pos, height, node) {
        /**Check if node at position pos exists.*/
        let left = 0n, right = (1n << BigInt(height - 1)) - 1n;

        for (let i = 0; i < height - 1; i++) {
            const mid = (left + right + 1n) / 2n;
            if (pos >= mid) {
                node = node.right;
                left = mid;
            } else {
                node = node.left;
                right = mid - 1n;
            }
        }

        return node !== null;
    }

    // Find height of tree
    let height = 0;
    let node = root;
    while (node) {
        height++;
        node = node.left;
    }

    // Binary search on number of nodes
    let low = 1n << BigInt(height - 1);    // 2^(h-1)
    let high = (1n << BigInt(height)) - 1n;  // 2^h - 1

    while (low <= high) {
        const mid = (low + high + 1n) / 2n;
        if (exists(mid, height, root)) {
            low = mid;
        } else {
            high = mid - 1n;
        }
    }

    return Number(low);
}

// Test cases
const root1 = new TreeNode(1);
root1.left = new TreeNode(2);
root1.right = new TreeNode(3);
root1.left.left = new TreeNode(4);
root1.left.right = new TreeNode(5);

console.log("Example 1 node count:", countNodes(root1));  // 5

const single = new TreeNode(1);
console.log("Example 2 node count:", countNodes(single));  // 1

console.log("Example 3 node count:", countNodes(null));  // 0

Rust

count_complete_tree_nodes_binary_search.rs

use std::cell::RefCell;
use std::rc::Rc;

#[derive(Debug)]
pub struct TreeNode {
    pub val: i32,
    pub left: Option<Rc<RefCell<TreeNode>>>,
    pub right: Option<Rc<RefCell<TreeNode>>>,
}

impl TreeNode {
    pub fn new(val: i32) -> Self {
        TreeNode {
            val,
            left: None,
            right: None,
        }
    }
}

/**
 * Count nodes in complete binary tree using binary search on node positions.
 * Uses existence check for node at each possible position.
 * Time: O(log² n), Space: O(log n) for recursion
 */
pub fn count_nodes(root: Option<Rc<RefCell<TreeNode>>>) -> i32 {
    if root.is_none() {
        return 0;
    }

    let root = root.unwrap();

    // Find height of tree
    let mut height = 0;
    let mut node = Some(root.clone());
    while let Some(n) = node.clone() {
        height += 1;
        let n_ref = n.borrow();
        node = n_ref.left.clone();
    }

    // Binary search on number of nodes
    let mut low = 1i64 << (height - 1);
    let mut high = (1i64 << height) - 1;

    while low <= high {
        let mid = (low + high + 1) / 2;
        if exists(mid, height, Some(root.clone())) {
            low = mid;
        } else {
            high = mid - 1;
        }
    }

    low as i32
}

fn exists(pos: i64, height: i32, mut node: Option<Rc<RefCell<TreeNode>>>) -> bool {
    /**Check if node at position pos exists.*/
    let mut left = 0i64;
    let mut right = (1i64 << (height - 1)) - 1;

    for _ in 0..height - 1 {
        let mid = (left + right + 1) / 2;

        if let Some(n) = node {
            let n_ref = n.borrow();
            if pos >= mid {
                node = n_ref.right.clone();
                left = mid;
            } else {
                node = n_ref.left.clone();
                right = mid - 1;
            }
        }
    }

    node.is_some()
}

fn main() {
    println!("Example 1: Count complete tree nodes with binary search");
}

Go

count_complete_tree_nodes_binary_search.go

package main

import "fmt"

/**
 * Definition for a binary tree node.
 */
type TreeNode struct {
    Val   int
    Left  *TreeNode
    Right *TreeNode
}

/**
 * Count nodes in complete binary tree using binary search on node positions.
 * Uses existence check for node at each possible position.
 * Time: O(log² n), Space: O(log n) for recursion
 */
func countNodes(root *TreeNode) int {
    if root == nil {
        return 0
    }

    // Find height of tree
    height := 0
    node := root
    for node != nil {
        height++
        node = node.Left
    }

    // Binary search on number of nodes
    low := int64(1) << (height - 1)
    high := (int64(1) << height) - 1

    for low <= high {
        mid := (low + high + 1) / 2
        if exists(mid, height, root) {
            low = mid
        } else {
            high = mid - 1
        }
    }

    return int(low)
}

func exists(pos int64, height int, root *TreeNode) bool {
    /**Check if node at position pos exists.*/
    left := int64(0)
    right := (int64(1) << (height - 1)) - 1
    node := root

    for i := 0; i < height-1; i++ {
        mid := (left + right + 1) / 2
        if pos >= mid {
            node = node.Right
            left = mid
        } else {
            node = node.Left
            right = mid - 1
        }
    }

    return node != nil
}

func main() {
    fmt.Println("Example 1: Count complete tree nodes with binary search")
}

Approach 3: Space-Optimized Variant

✓ Simple

A third approach demonstrating an alternative technique for solving this problem. This implementation optimizes either time or space complexity compared to the previous approaches.

⏱ Time O(n) Optimized complexity 💾 Space O(1) Efficient space usage

Pseudocode

function approach3():
    // Implementation approach goes here

Solution Code

Python

count_complete_tree_nodes_space_optimized.py

"""
Solution for Count Complete Tree Nodes
"""

def solve():
    """Implementation for approach 3 of Count Complete Tree Nodes"""
    pass

if __name__ == "__main__":
    print("Solution ready")

C++

count_complete_tree_nodes_space_optimized.cpp

#include <bits/stdc++.h>
using namespace std;

// Solution for Count Complete Tree Nodes
// Approach 3: Implementation

int main() {{
    // Main implementation goes here
    return 0;
}}

Java

CountCompleteTreeNodesSpaceOptimized.java

/**
 * Solution for Count Complete Tree Nodes
 * Approach 3
 */
public class CountCompleteTreeNodesSpaceOptimized {{

    public static void main(String[] args) {{
        // Implementation goes here
    }}
}}

JavaScript

count_complete_tree_nodes_space_optimized.js

/**
 * Solution for Count Complete Tree Nodes
 * Approach 3
 */

function solve() {{
    // Implementation goes here
}}

module.exports = solve;

Rust

count_complete_tree_nodes_space_optimized.rs

/// Solution for Count Complete Tree Nodes
/// Approach 3

fn main() {{
    println!("Solution implementation");
}}

Go

count_complete_tree_nodes_space_optimized.go

package main

import "fmt"

// Solution for Count Complete Tree Nodes
// Approach 3

func main() {{
    fmt.Println("Solution implementation")
}}

Related Problems

• Maximum Depth of Binary Tree ↗ Easy #104
• Minimum Depth of Binary Tree ↗ Easy #111
• Maximum Nary Tree Depth ↗ Easy #559

Interview Tips

Key trade-offs to discuss

• Why O(log² n)? Exploit complete tree structure; exploit height in both approaches.
• Level Calculation: Simpler logic, uses perfect subtree formula directly.
• Binary Search: More complex but searches for actual position; demonstrates binary search skill.
• Complete Tree Property: Key insight is that checking left/right heights determines subtree structure.

← Previous
#221 Maximal Square Next
#224 Basic Calculator →