Count Complete Tree Nodes Visualizer & Step-by-Step Algorithm Solution

Count nodes in a complete binary tree in less than O(n) time by comparing left and right subtree heights.

Category: trees | Difficulty: Medium

Tags: DFS, Binary Tree, Binary Search, Tree Height, Complete Tree

Count Complete Tree Nodes

1
2
4
5
3
6
100%
Initialization
1/13
Explanation

Start countNodes on complete binary tree with root: Node(1).

Source Code
1function countNodes(root) {
2 if (!root) return 0;
3 let lHeight = 0, rHeight = 0;
4 let l = root, r = root;
5 while (l) { lHeight++; l = l.left; }
6 while (r) { rHeight++; r = r.right; }
7 if (lHeight === rHeight) return (1 << lHeight) - 1;
8 return 1 + countNodes(root.left) + countNodes(root.right);
9}