Source: https://guthlabs.ai/docs/instruments/binary-tree-heap-visualizer-property-calculator/

instrument / verified-clean

# Binary Tree / Heap Visualizer & Property Calculator

The current ledger marks this instrument verified clean within the source-bound verification corpus.

Status: **VERIFIED_CLEAN**Lifecycle: **verified-clean**

## Inspectable records

[01**Overview**Purpose and lifecycle](<https://guthlabs.ai/docs/instruments/binary-tree-heap-visualizer-property-calculator/>)[02**Mechanism**Method and assumptions](<https://guthlabs.ai/docs/instruments/binary-tree-heap-visualizer-property-calculator/mechanism/>)[03**Implementation**Binding and validation](<https://guthlabs.ai/docs/instruments/binary-tree-heap-visualizer-property-calculator/implementation/>)[04**Qualification**Evidence and errata](<https://guthlabs.ai/docs/instruments/binary-tree-heap-visualizer-property-calculator/qualification/>)

## Ledger state

The current ledger marks this instrument verified clean within the source-bound verification corpus.

**Area**: Computing & Information

**Tranche**: tranche-6

**Evidence ID**: t6-098

**Ledger rows**: 1

No ledger note is attached.

## Review findings

The core heap comparator is standard once the selected heap type and array-to-tree mapping are defined. The specification is not sufficiently precise to verify one unique implementation, so it requires review before release.

### Formula and scope findings

- height=floor(log2(n)) is valid only for a complete binary tree when height means number of edges on the longest root-to-leaf path; it is not valid for an arbitrary BST or binary tree.

- The notation ⌊log2(n)⌉ is ambiguous: it may mean rounding to nearest integer rather than flooring.

- The construction rule is unspecified. An input array may mean level-order placement, sequential BST insertion, or an already linked tree; these produce different trees and heights.

- The balance-factor formula is missing. A standard convention is balance_factor(node)=height(left_subtree)-height(right_subtree), with empty-subtree height=-1 for edge-based heights.

- The heap condition must be applied to every existing parent-child edge, using either parent<=child for a min-heap or parent>=child for a max-heap; the phrase '(or)' does not define which mode is active.

### Unit assumptions

- n is a dimensionless count of nodes; log2(n) has no physical units.

- The test vectors use height measured in edges, so an empty tree has height=-1, a one-node tree has height=0, and a three-level complete tree has height=2.

- All values in each array are mutually comparable and use the same ordering; no numeric unit conversion is performed.

- For heap vectors, arrays are interpreted as level-order node placement. For the BST vector, values are inserted sequentially using the standard rule: smaller values go left and larger values go right.

## Boundary hardening

### Recorded hazards

- log2(0) causes an undefined-value or division/domain error unless the empty tree is handled before applying the formula.

- Using floor(log2(n)) for a non-complete tree gives an incorrect height; the implementation must compute the longest root-to-leaf path for arbitrary trees.

- A one-based heap-index implementation must use child indices 2i and 2i+1, while a zero-based implementation must use 2i+1 and 2i+2; mixing conventions can create invalid edges or missed checks.

- Duplicate BST values require an explicit policy, such as reject, always insert left, or always insert right.

- A balance factor needs a declared sign convention and empty-subtree height convention; otherwise reported values are ambiguous.

- Heap validation should handle missing children and should report which parent-child edge violates the selected min-heap or max-heap comparator.

- If arbitrary numeric strings, mixed units, NaN, or incomparable values are accepted, ordering and heap validation are not well-defined.

- The honest label is empty; the instrument should state the construction mode, height convention, balance-factor definition, duplicate policy, and that the complete-tree height shortcut is not applicable to arbitrary BSTs.

## Errata and corrections

No applied erratum is attached to this unique-name record.

## Inspectable example

4 review vectors are recorded. One source-bound sample is shown below.

````
{
  "inputs": {
    "array": [
      1,
      3,
      2,
      7,
      6,
      5
    ],
    "tree_type": "min-heap",
    "construction": "level-order",
    "height_convention": "edges",
    "balance_convention": "left_height_minus_right_height"
  },
  "expected_outputs": {
    "nodes_by_level": [
      [
        1
      ],
      [
        3,
        2
      ],
      [
        7,
        6,
        5
      ]
    ],
    "height_edges": 2,
    "balance_factors_by_value": {
      "1": 0,
      "2": 1,
      "3": 0,
      "5": 0,
      "6": 0,
      "7": 0
    },
    "heap_valid": true,
    "violations": []
  },
  "working": "n=6. Complete-tree height = floor(log2(6)) = floor(2.5849625007) = 2 edges. Levels are [1], [3,2], [7,6,5], so there are 3 levels and height 3-1=2. Heap checks: 1<=3, 1<=2, 3<=7, 3<=6, and 2<=5; all are true. Balance factors: BF(1)=1-1=0; BF(3)=0-0=0; BF(2)=0-(-1)=1; each leaf has 0-0=0. Therefore the min-heap is valid."
}
````

## Related workflows

No source-defined multi-instrument workflow membership is recorded.

## Sources and evidence

These pointers bind the page to evidence. They do not grant authority or collapse verification into deployment.

- `VERIFIED_LEDGER.json · VERIFIED_CLEAN`

- `evidence-tranche6/tranche6-results.json`