176. Check if a Binary Tree Is a Valid Heap

Given a binary tree, print 'Yes' if it is a valid max-heap - meaning it is a complete binary tree (every level is fully filled left to right, except possibly the last, whose missing nodes are all at the end) and every node's value is greater than or equal to both its children's values - otherwise print 'No'. The tree is given as space-separated level-order tokens, where 'N' means no node there: the first token is the root, then for each node dequeued in level order you read its left-child token then its right-child token (if input runs out early, remaining children are treated as N).

Input: A single line contains the binary tree's space-separated level-order tokens, where 'N' denotes a missing node: the first token is the root, and then for each node dequeued in level order its left-child token then its right-child token follows (missing trailing tokens count as N). Output: Print 'Yes' if the tree is a valid max-heap (complete and heap-ordered), otherwise print 'No'.

1 <= number of nodes <= 10^5

Completeness is a STRUCTURAL property (about the tree's SHAPE) while heap-order is a VALUE property (about the numbers themselves) - a valid heap needs both simultaneously, and conflating the two checks is a common source of incomplete solutions.

Check whether a binary tree satisfies both requirements of a valid max-heap: being a complete tree, AND having every parent greater than or equal to its children. Brute force: There isn't really a meaningfully 'slower' alternative - checking these two properties (completeness, then heap-order) directly via traversal IS the natural, direct approach. Optimised: A single level-order (BFS) pass can check completeness (watching for a real node appearing after a gap) while a separate simple recursive pass checks heap-order at every node - both checks are linear and independent, so combined they're still O(n) overall.

Run a standard queue-based BFS completeness check: once any node is found with a missing left child (or is itself missing), every node processed afterward in the queue must also have no children, otherwise the tree isn't complete. Then run a separate DFS pass purely to check the max-heap ordering property, that every node's value is >= both its children's values. This avoids the exponential blowup of materializing a full positional array by working directly off the tree's actual nodes. Time: O(n) Space: O(n)

Do a level-order traversal down to the tree's maximum depth, explicitly materializing an array indexed by the standard complete-binary-tree position formula (root at 1, children of node i at 2i and 2i+1), inserting placeholders for every missing slot at every level. Then scan the array for gaps (a filled slot appearing after an empty one means the tree isn't complete) and separately check that every filled parent slot is >= its filled children slots. This works for a genuinely complete or near-complete tree, but for a skewed tree of height h it forces an array of size up to 2^h, which can blow up to exponential size well before reaching the given node count. Time: O(2^h) worst case Space: O(2^h) worst case

First do one traversal purely to count the total number of nodes n. Then do a single recursive DFS that, for each node, computes its 1-indexed position as if the tree were stored in an array (root = 1, left child = 2*index, right child = 2*index+1) and simultaneously checks both that this index never exceeds the total node count (which is exactly the completeness condition) and that the node's value is >= its children's values, short-circuiting to false the moment either check fails. This merges what the two-pass approach did separately into one pass, and replaces its explicit BFS queue with only the recursion stack, which is bounded by the tree's height rather than its full size. Time: O(n) Space: O(h)

1. Check COMPLETENESS first: during a level-order traversal, once you encounter one missing child, every node processed AFTER that point must also be missing - any real node appearing after a gap immediately fails completeness. 2. Separately, check the HEAP-ORDER property: at every internal node, its value must be >= both its children's values. 3. Both checks must pass for the tree to be a valid max-heap.

Time: O(n) - one pass for completeness, one pass for heap-order, both linear. Space: O(n) for the BFS queue during the completeness check, plus O(h) for the recursion stack during the heap-order check.

a single-node tree (trivially valid), a tree that is heap-ordered but not complete (a real node appears after a gap in level order), and up to 10^5 nodes for performance.

Be ready to explain BOTH conditions clearly and why NEITHER alone is sufficient - a tree could be complete but violate heap-order, or satisfy heap-order everywhere but not be complete (have gaps in the middle), and both failures need to be checked independently.