Sponsored
Sponsored
This approach uses a level-order traversal technique with the help of a queue to check if the binary tree is complete. In a complete binary tree, once a null node is encountered while doing a level order traversal, all subsequent nodes must also be null to satisfy completeness.
Time Complexity: O(n), where n is the number of nodes in the tree. We traverse each node once.
Space Complexity: O(n), where n is the number of nodes, used for the queue storage.
1import java.util.LinkedList;
2import java.util.Queue;
3
4class TreeNode {
5 int val;
6 TreeNode left;
7 TreeNode right;
8 TreeNode(int x) { val = x; }
9}
10
11class Solution {
12 public boolean isCompleteTree(TreeNode root) {
13 if (root == null) return true;
14 Queue<TreeNode> queue = new LinkedList<>();
15 queue.offer(root);
16 boolean encounteredNull = false;
17 while (!queue.isEmpty()) {
18 TreeNode current = queue.poll();
19 if (current == null) {
20 encounteredNull = true;
21 } else {
22 if (encounteredNull) return false;
23 queue.offer(current.left);
24 queue.offer(current.right);
25 }
26 }
27 return true;
28 }
29}The Java solution follows a similar logic to C++. It uses a LinkedList as a queue to manage node processing. The 'encounteredNull' flag is used to verify the sequence property of a complete binary tree.
This approach utilizes depth-first search to gather information regarding the number of nodes and their indices. Using these, we check the compactness of the tree at each level to ensure all nodes fit the complete binary tree property.
Time Complexity: O(n).
Space Complexity: O(n), due to recursive stack usage.
1
JavaScript uses DFS after counting nodes to ensure node indices stay within a plausible complete binary tree range.