Question

Formatted question description: https://leetcode.ca/all/222.html

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

According to Wikipedia, every level, except possibly the last, is completely filled in a complete binary tree, and all nodes in the last level are as far left as possible. It can have between 1 and 2^h nodes inclusive at the last level h.

Design an algorithm that runs in less than O(n) time complexity.

Example 1:

Input: root = [1,2,3,4,5,6]
Output: 6

Example 2:

Input: root = []
Output: 0

Example 3:

Input: root = [1]
Output: 1

Constraints:

The number of nodes in the tree is in the range [0, 5 * 10⁴].
0 <= Node.val <= 5 * 10⁴
The tree is guaranteed to be complete.

Algorithm

First, we need a getHeight function, which is used to count the maximum height of the left subtree of the current node.

Call the getHeight function on the current node to get the maximum height h of the left subtree. If returned is -1, it means that the current node does not exist and returns 0 directly.
Otherwise, call the getHeight function on the right child.
- If the return value is h-1, it means that the left sub-tree is a perfect binary tree, and the number of nodes in the left sub-tree is 2^h-1. Adding the current node, there are 2^h in total, that is, 1<<h,
  - then, add the return value of calling the recursive function on the right child node.
- If the return value of calling the getHeight function on the right subnode is not h-1, it means that the right subtree must be a perfect tree, and the height is h-1,
  - then the number of summary points is 2^(h-1) -1, plus the current node is 2^(h-1), that is, 1<<(h-1), and then add the return value of calling the recursive function on the left child node

Code

public class Count_Complete_Tree_Nodes {
    /**
     * Definition for a binary tree node.
     * public class TreeNode {
     *     int val;
     *     TreeNode left;
     *     TreeNode right;
     *     TreeNode(int x) { val = x; }
     * }
     */

    public class Solution_optimize {

        public int countNodes(TreeNode root) {

            int res = 0;
            int h = getHeight(root); // here h is actually h-1

            if (h < 0) return 0;

            if (getHeight(root.right) == h - 1) {
                return (1 << h) + countNodes(root.right);
            } else { // getHeight(root.right) == h - 2
                return (1 << (h - 1)) + countNodes(root.left);
            }
        }

        int getHeight(TreeNode node) {
            return node != null ? (1 + getHeight(node.left)) : -1;
        }
    }

    public class Solution {
        public int countNodes(TreeNode root) {
            if (root == null) {
                return 0;
            }

            int leftHeight = findLeftHeight(root);
            int rightHeight = findRightHeight(root);

            if (leftHeight == rightHeight) {
                return (2 << (leftHeight - 1)) - 1;
            }

            return 1 + countNodes(root.left) + countNodes(root.right);
        }

        private int findLeftHeight(TreeNode root) {
            if (root == null) {
                return 0;
            }

            int height = 1;

            while (root.left != null) {
                height++;
                root = root.left;
            }

            return height;
        }

        private int findRightHeight(TreeNode root) {
            if (root == null) {
                return 0;
            }

            int height = 1;

            while (root.right != null) {
                height++;
                root = root.right;
            }

            return height;
        }
    }
}

############

/**
 * 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;
 *     }
 * }
 */
class Solution {
    public int countNodes(TreeNode root) {
        if (root == null) {
            return 0;
        }
        int left = depth(root.left);
        int right = depth(root.right);
        if (left == right) {
            return (1 << left) + countNodes(root.right);
        }
        return (1 << right) + countNodes(root.left);
    }

    private int depth(TreeNode root) {
        int d = 0;
        for (; root != null; root = root.left) {
            ++d;
        }
        return d;
    }
}

// OJ: https://leetcode.com/problems/count-complete-tree-nodes/
// Time: O(H^2)
// Space: O(H)
class Solution {
    int countLeft(TreeNode *root) {
        int cnt = 0;
        for (; root; ++cnt, root = root->left);
        return cnt;
    }
    int countRight(TreeNode *root) {
        int cnt = 0;
        for (; root; ++cnt, root = root->right);
        return cnt;
    }
public:
    int countNodes(TreeNode* root) {
        if (!root) return 0;
        int left = countLeft(root), right = countRight(root);
        if (left == right) return (1 << left) - 1;
        return countNodes(root->left) + countNodes(root->right) + 1;
    }
};

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def countNodes(self, root: Optional[TreeNode]) -> int:
        def depth(root):
            d = 0
            while root:
                d += 1
                root = root.left
            return d

        if root is None:
            return 0
        left, right = depth(root.left), depth(root.right)
        if left == right:
            # left child subtree: (1<<left)-1
            # plus root: +1
            # so total except right subtree: (1<<left)
            return (1 << left) + self.countNodes(root.right)
        else: # left = right+1
            return (1 << right) + self.countNodes(root.left)

############

'''
>>> 2 ** 3
8
>>> 3 ** 2
9
'''


# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
  def getHeight(self, root):
    height = 0
    while root:
      height += 1
      root = root.left
    return height

  def countNodes(self, root):
    count = 0
    while root:
      l, r = map(self.getHeight, (root.left, root.right))
      if l == r:
        count += 2 ** l
        root = root.right
      else:
        count += 2 ** r
        root = root.left
    return count

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func countNodes(root *TreeNode) int {
	if root == nil {
		return 0
	}
	left, right := depth(root.Left), depth(root.Right)
	if left == right {
		return (1 << left) + countNodes(root.Right)
	}
	return (1 << right) + countNodes(root.Left)
}

func depth(root *TreeNode) (d int) {
	for ; root != nil; root = root.Left {
		d++
	}
	return
}

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number}
 */
var countNodes = function (root) {
    const depth = root => {
        let d = 0;
        for (; root; root = root.left) {
            ++d;
        }
        return d;
    };
    if (!root) {
        return 0;
    }
    const left = depth(root.left);
    const right = depth(root.right);
    if (left == right) {
        return (1 << left) + countNodes(root.right);
    }
    return (1 << right) + countNodes(root.left);
};

﻿/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left;
 *     public TreeNode right;
 *     public TreeNode(int val=0, TreeNode left=null, TreeNode right=null) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
public class Solution {
    public int CountNodes(TreeNode root) {
        if (root == null) {
            return 0;
        }
        int left = depth(root.left);
        int right = depth(root.right);
        if (left == right) {
            return (1 << left) + CountNodes(root.right);
        }
        return (1 << right) + CountNodes(root.left);
    }

    private int depth(TreeNode root) {
        int d = 0;
        for (; root != null; root = root.left) {
            ++d;
        }
        return d;
    }
}

use std::cell::RefCell;
use std::rc::Rc;

impl Solution {
    pub fn count_nodes(root: Option<Rc<RefCell<TreeNode>>>) -> i32 {
        if let Some(node) = root {
            let node = node.borrow();
            let left = Self::depth(&node.left);
            let right = Self::depth(&node.right);
            if left == right {
                Self::count_nodes(node.right.clone()) + (1 << left)
            } else {
                Self::count_nodes(node.left.clone()) + (1 << right)
            }
        } else {
            0
        }
    }

    fn depth(root: &Option<Rc<RefCell<TreeNode>>>) -> i32 {
        if let Some(node) = root {
            Self::depth(&node.borrow().left) + 1
        } else {
            0
        }
    }
}

222 - Count Complete Tree Nodes

Question

Algorithm

Code

All Problems

All Solutions

Welcome to Subscribe On Youtube

Question

Algorithm

Code

All Problems

All Solutions