Evaluate a Boolean Formula AST

You are given the root of a simplified Abstract Syntax Tree (AST) that encodes a boolean formula. Your task is to write an evaluator that traverses the tree and returns the resulting boolean value.

The tree nodes are represented as JSON objects and can be one of the following kinds:

1. boolean – a literal boolean value:

   {"type": "boolean", "value": true}
   

2. number – a literal integer:

   {"type": "number", "value": 3}
   

3. binaryOp – a binary logical operation. The field op is either "AND" or "OR", and both left and right are child subtrees:

   {
     "type": "binaryOp",
     "op": "AND",
     "left": <subtree>,
     "right": <subtree>
   }
   

4. relationalOp – a relational comparison. The field op is one of "==", "<", ">", and both left and right are child subtrees:

   {
     "type": "relationalOp",
     "op": "<",
     "left": <subtree>,
     "right": <subtree>
   }
   

5. variable – a named placeholder whose value is looked up from a supplied environment:

   {"type": "variable", "name": "x"}
   

Type Conversion Rules

When the evaluator needs a boolean value:

• a boolean node yields its stored value directly;
• a number node is interpreted as false when its value is 0 and true for any non-zero value.

When the evaluator needs an integer value:

• a number node yields its stored integer directly;

• a boolean node is treated as 1 for true and 0 for false.

• AND and OR evaluate both operands as booleans and produce a boolean result.

• ==, <, and > first convert both operands to integers and then perform the comparison, returning a boolean.

• Variable values are always either an integer or a boolean.

• You may assume the tree is well-formed and every variable referenced in the AST is present in the environment.

Input Format

The input is provided via standard input as a single JSON object with two fields:

{
  "ast": <root of the AST>,
  "env": {
    "x": true,
    "y": 3
  }
}

The env dictionary maps variable names to their values. It may be empty or absent.

Output Format

Print a single line containing either true or false.

Constraints

• Total number of AST nodes: 1 <= n <= 100,000
• Integer literals and environment values lie in the range [-1,000,000,000, 1,000,000,000]
• The tree depth is such that a recursive solution in a typical runtime (e.g., Python) will not overflow the call stack; an iterative traversal is also acceptable.

Example 1

Input: {"ast":{"type":"binaryOp","op":"AND","left":{"type":"boolean","value":false},"right":{"type":"boolean","value":true}}}

Output: false

Explanation: false AND true evaluates to false.

Example 2

Input: {"ast":{"type":"relationalOp","op":">","left":{"type":"number","value":5},"right":{"type":"number","value":3}}}

Output: true

Example 3

Input: {"ast":{"type":"binaryOp","op":"OR","left":{"type":"number","value":0},"right":{"type":"boolean","value":true}}}

Output: true

Explanation: 0 is falsy, true is truthy, so false OR true is true.

Example 4

Input: {"ast":{"type":"relationalOp","op":"==","left":{"type":"boolean","value":false},"right":{"type":"number","value":0}}}

Output: true

Explanation: false converts to 0, and 0 == 0 is true.

Example 5

Input: {"ast":{"type":"binaryOp","op":"AND","left":{"type":"variable","name":"a"},"right":{"type":"relationalOp","op":"<","left":{"type":"variable","name":"b"},"right":{"type":"number","value":8}}},"env":{"a":true,"b":4}}

Output: true

Constraints

• 1 <= total number of AST nodes <= 100,000
• -1,000,000,000 <= integer values <= 1,000,000,000
• The AST is well-formed and all referenced variables exist in the environment.
• The tree depth is within safe recursion limits for typical runtimes.