Evaluate Boolean Binary Tree

🏠 ⬅️ ➡️

You are given the root of a full binary tree with the following properties:

  • Leaf nodes have either the value 0 or 1, where 0 represents False and 1 represents True.
  • Non-leaf nodes have either the value 2 or 3, where 2 represents the boolean OR and 3 represents the boolean AND.

The evaluation of a node is as follows:

  • If the node is a leaf node, the evaluation is the value of the node, i.e. True or False.
  • Otherwise, evaluate the node's two children and apply the boolean operation of its value with the children's evaluations.

Return the boolean result of evaluating the root node.

A full binary tree is a binary tree where each node has either 0 or 2 children.

A leaf node is a node that has zero children.

Example 1:

Input: root = [2,1,3,null,null,0,1] Output: true Explanation: The above diagram illustrates the evaluation process. The AND node evaluates to False AND True = False. The OR node evaluates to True OR False = True. The root node evaluates to True, so we return true.

Example 2:

Input: root = [0] Output: false Explanation: The root node is a leaf node and it evaluates to false, so we return false.

Constraints:

  • The number of nodes in the tree is in the range [1, 1000].
  • 0 <= Node.val <= 3
  • Every node has either 0 or 2 children.
  • Leaf nodes have a value of 0 or 1.
  • Non-leaf nodes have a value of 2 or 3.
Note: This problem is from LeetCode.
❌ Compiled
❌ Executed
❌ Correct 
program main
    use, intrinsic :: iso_fortran_env, only : error_unit, output_unit
    implicit none
    integer, parameter :: n = 7
    integer, dimension(n) :: values = [2, 1, 3, 0, 0, 0, 1]
    type(binary_tree), pointer :: root
    logical :: result

    call build_tree(values, root)
    result = evaluate_tree(root)
    write (output_unit, '(*(g0))') 'Result: ', result

contains

    subroutine build_tree(values, root)
        implicit none
        integer, dimension(:), intent(in) :: values
        type(binary_tree), pointer, intent(out) :: root
        integer :: i, j, k

        allocate(root)
        if (size(values) == 1) then
            root%value = values(1)
        else
            root%value = values(1)
            do i = 2, size(values) - 1, 2
                allocate(root%left)
                call build_tree(values(i:i+1), root%left)
            end do
            do i = 3, size(values) - 1, 2
                allocate(root%right)
                call build_tree(values(i:i+1), root%right)
            end do
        end if
    end subroutine build_tree

    function evaluate_tree(root) result(result)
        implicit none
        type(binary_tree), pointer, intent(in) :: root
        logical :: result

        if (.not. associated(root)) then
            result = .false.
        else if (associated(root%left, root%right)) then
            result = evaluate_tree(root%left) .and. evaluate_tree(root%right)
        else if (associated(root%left)) then
            result = evaluate_tree(root%left) .or. root%value == 1
        else if (associated(root%right)) then
            result = evaluate_tree(root%right) .or. root%value == 1
        else
            result = root%value == 1
        end if
    end function evaluate_tree

end program main

type :: binary_tree
    integer :: value
    class(binary_tree), pointer :: left => null(), right => null()
end type binary_tree
❌ Compiled
❌ Executed
❌ Correct 
module BinaryTreeEvaluation
    implicit none
    private
    public :: evaluate_binary_tree
contains
    logical function evaluate_binary_tree(root) result(result)
        type(binary_tree_node), pointer, intent(in) :: root
        logical :: left_result, right_result

        if (.not. associated(root)) then
            result = .false.
            return
        end if

        if (root%left_child%is_leaf) then
            left_result = root%left_child%value == 1
        else
            left_result = evaluate_binary_tree(root%left_child)
        end if

        if (root%right_child%is_leaf) then
            right_result = root%right_child%value == 1
        else
            right_result = evaluate_binary_tree(root%right_child)
        end if

        select case (root%value)
            case (2)
                result = left_result .or. right_result
            case (3)
                result = left_result .and. right_result
            case default
                result = .false.
        end select
    end function evaluate_binary_tree

    type binary_tree_node
        integer :: value = 0
        logical :: is_leaf = .false.
        type(binary_tree_node), pointer :: left_child => null()
        type(binary_tree_node), pointer :: right_child => null()
    end type binary_tree_node
end module BinaryTreeEvaluation

program test_binary_tree_evaluation
    use BinaryTreeEvaluation
    implicit none
    type(binary_tree_node), target :: root
    logical :: result

    ! Example 1
    root%value = 2
    root%left_child%value = 1
    root%right_child%value = 3
    root%left_child%left_child%value = 0
    root%left_child%right_child%value = 1
    result = evaluate_binary_tree(root)
    write (*,*) "Example 1: ", result

    ! Example 2
    root%value = 0
    result = evaluate_binary_tree(root)
    write (*,*) "Example 2: ", result
end program test_binary_tree_evaluation
🌐 Data from online sources 
def evalTree(root: 'TreeNode') -> bool:
    if not root.left and not root.right:
        return root.val == 1
    left = evalTree(root.left)
    right = evalTree(root.right)

    if root.val == 2:
        return left or right
    return left and right

This problem uses a binary tree to calculate boolean values.

The algorithm for this problem is a recursive depth-first search. 1. If the current node is a leaf node, return its value (True / False). 2. If the current node is a non-leaf node, recursively compute the values of its left and right children. 3. If the current node is an OR node, return the result of left || right. If it's an AND node, return the result of left && right.

The base case here is when the node is a leaf node, and the recursion will stop, returning its boolean value. At each level of recursion, it will evaluate the operator associated with the node and build up the final result.

🌐 Data from online sources 
bool evalTree(TreeNode* root) {
    if (!root->left && !root->right)
        return root->val;
    bool left = evalTree(root->left);
    bool right = evalTree(root->right);

    if (root->val == 2)
        return left || right;
    return left && right;
}

This problem uses a binary tree to calculate boolean values.

The algorithm for this problem is a recursive depth-first search. 1. If the current node is a leaf node, return its value (True / False). 2. If the current node is a non-leaf node, recursively compute the values of its left and right children. 3. If the current node is an OR node, return the result of left || right. If it's an AND node, return the result of left && right.

The base case here is when the node is a leaf node, and the recursion will stop, returning its boolean value. At each level of recursion, it will evaluate the operator associated with the node and build up the final result.