Xuanken Tay

Software engineer who likes statistics, machine learning, DevOps and the cloud

less than 1 minute read

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

This should be done in O((logn)2).

Constraints

  • n ≤ 100,000 where n is the number of nodes in root

https://binarysearch.com/problems/Count-Nodes-in-Complete-Binary-Tree

ExamplesPermalink

Example 1Permalink

Input

  • root =
example1Root 0 1 1 2 0->1 2 3 0->2 3 4 1->3 4 5 1->4

Output

  • answer = 5

Example 2Permalink

Input

  • root =
example2Root 0 1 1 2 0->1 2 3 0->2 3 4 1->3 4 5 1->4 5 6 2->5 6 7 2->6

Output

  • answer = 7

SolutionPermalink

/**
* class Tree {
* public:
* int val;
* Tree *left;
* Tree *right;
* };
*/
int solve(Tree *root)
{
int nLeft = 0, nRight = 0;
Tree *left = root, *right = root;
for (Tree *node = root; node; node = node->left, nLeft++)
;
for (Tree *node = root; node; node = node->right, nRight++)
;
if (nLeft == nRight)
{
return (1 << nLeft) - 1;
}
return 1 + solve(root->left) + solve(root->right);
}
view raw Count-Nodes-in-Complete-Binary-Tree.cpp hosted with ❤ by GitHub

Leave a comment

Read more

Binary Search Tree Typo

less than 1 minute read

You are given a binary tree root which is almost a binary search tree except two nodes’ values have been swapped. Return the original binary search tree.

Longest Tree Path

less than 1 minute read

Given a binary tree root, return the longest path between any two nodes in the tree.

Top View of a Tree

less than 1 minute read

Given a binary tree root, return the top view of the tree, sorted left-to-right.