Size of a Packed Tree

Easy

You are given the root of a binary tree that is packed: every level except possibly the last is completely full, and the nodes of the last level sit side by side starting from the leftmost position. Return the number of nodes in the tree. Visiting every node takes O(n). Use the shape of the tree to do better.

Example 1

root=tree_node([4, 9, 2, 7, 1]) → 5

The top two levels are full (3 nodes), and the bottom level has two nodes packed to the left: 5 in total.

Example 2

root=tree_node([]) → 0

An empty tree has zero nodes.

Example 3

root=tree_node([6, 3, 8, 0, 5, 2, 9]) → 7

All three levels are full: 1 + 2 + 4 = 7.

Constraints

0 ≤ number of nodes ≤ 5·10⁴
0 ≤ Node.val ≤ 5·10⁴
The tree is packed as described above

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Bit Manipulation Tree Binary Search Binary Tree

Similar problems

Nearest Value in a Search Tree Easy Pair Across Two Search Trees Medium Floor and Ceiling in a Search Tree Medium Left, Node, Right Easy Identical Trees Easy

Input

root=tree_node([4, 9, 2, 7, 1])

Expected

Run checks the first 3 tests in your browser. Submit checks all 49 tests on the server, hidden ones included.