Count Complete Tree Nodes | Solution (Explained)
LeetCode 222. Count Complete Tree Nodes is a medium problem if you go by the naive solution. To upgrade the time complexity from O(N) though, we need some more tricks up our sleeves. In this blog I explore both the solutions. Problem Link.
0. Count Complete Tree Nodes: Naïve Solution
0.0 Code
class Solution: def countNodes(self, root: Optional[TreeNode]) -> int: def dfs(node): if not node: return 0 return dfs(node.left) + dfs(node.right) + 1 return dfs(root)
0.1. Complexity Analysis
- Time: O(N) to visit all the nodes
- Space: O(LogN), the height of the recursion call stack, the height of binary tree.
1. Observations
A bit sick right now, will add the explanations later. Put a comment if I forget to put by the end of week 😛
2. Count Complete Tree Nodes: Optimized Solution
2.0. Code
class Solution: def countNodes(self, root: Optional[TreeNode]) -> int: def dfs(node): if not node: return 0 lh = get_height(node, 0) rh = get_height(node, 1) if lh == rh: return ((1 << lh) - 1) return dfs(node.left) + dfs(node.right) + 1 def get_height(node, i): count = 1 if i == 0: while (node := node.left): count += 1 else: while (node := node.right): count += 1 return count return dfs(root)
2.1. Complexity Analysis
- Time:
O(LogN * LogN)
. Each time, we either choose to go for thelh == rh
option OR the standard route. Either way we compute the depth inO(LogN)
time. This decision takes place for each height and not each node. Since we would bypass the computation a lot of times – due to thelh == rh
being followed. So,- depth computation:
O(LogN)
- #times depth is computed:
O(LogN)
- depth computation:
- Space:
O(LogN)
for the recursion call stack height.
Recommended Posts
Gas Station | InterviewBit | Solution Explained
June 13, 2022