Given a complete binary tree, count the number of nodes.
Note:
Definition of a complete binary tree from :
In a complete binary tree every level, except possibly the last, is completely filled, and all nodes in the last level are as far left as possible. It can have between 1 and 2h nodes inclusive at the last level h.
Constraints
Approach
Links
GeeksforGeeks
Leetcode
ProgramCreek
YouTube
Examples
Input:
[1, 2, 3, 4, 5, 6]
Output:
6
Solutions
// Definition for a binary tree node.
public class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode() {}
TreeNode(int val) {
this.val = val;
}
TreeNode(int val, TreeNode left, TreeNode right) {
this.val = val;
this.left = left;
this.right = right;
}
}
/**
* Time complexity : O(N)
* Space complexity : O(d)=O(logN) to keep the recursion stack,
* where d is a tree depth.
*/
class Solution {
public int countNodes(TreeNode root) {
if(root == null) return 0;
return 1 + countNodes(root.left) + countNodes(root.right);
}
}
/**
* Time complexity :
* Space complexity :
*/
class Solution {
public int countNodes(TreeNode root) {
if(root == null) return 0;
int left = getLeftHeight(root) + 1;
int right = getRightHeight(root) + 1;
if(left == right) {
return (2 << (left-1))-1;
}
return 1 + countNodes(root.left) + countNodes(root.right);
}
private int getLeftHeight(TreeNode node) {
if(node == null) return 0;
int height = 0;
while(node.left != null) {
height++;
node = node.left;
}
return height;
}
private int getRightHeight(TreeNode node) {
if(node == null) return 0;
int height = 0;
while(node.right != null) {
height++;
node = node.right;
}
return height;
}
}
