Last active
September 1, 2020 17:41
-
-
Save igor-brishkoski/af0d87098bb0dedcafc53aea3b2f0c26 to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
class Solution { | |
// Return tree depth in O(d) time. | |
public int computeDepth(TreeNode node) { | |
int d = 0; | |
while (node.left != null) { | |
node = node.left; | |
++d; | |
} | |
return d; | |
} | |
// Last level nodes are enumerated from 0 to 2**d - 1 (left -> right). | |
// Return True if last level node idx exists. | |
// Binary search with O(d) complexity. | |
public boolean exists(int idx, int d, TreeNode node) { | |
int left = 0, right = (int)Math.pow(2, d) - 1; | |
int pivot; | |
for(int i = 0; i < d; ++i) { | |
pivot = left + (right - left) / 2; | |
if (idx <= pivot) { | |
node = node.left; | |
right = pivot; | |
} | |
else { | |
node = node.right; | |
left = pivot + 1; | |
} | |
} | |
return node != null; | |
} | |
public int countNodes(TreeNode root) { | |
// if the tree is empty | |
if (root == null) return 0; | |
int d = computeDepth(root); | |
// if the tree contains 1 node | |
if (d == 0) return 1; | |
// Last level nodes are enumerated from 0 to 2**d - 1 (left -> right). | |
// Perform binary search to check how many nodes exist. | |
int left = 1, right = (int)Math.pow(2, d) - 1; | |
int pivot; | |
while (left <= right) { | |
pivot = left + (right - left) / 2; | |
if (exists(pivot, d, root)) left = pivot + 1; | |
else right = pivot - 1; | |
} | |
// The tree contains 2**d - 1 nodes on the first (d - 1) levels | |
// and left nodes on the last level. | |
return (int)Math.pow(2, d) - 1 + left; | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment