mutable struct BNode
    data::Int
    left::Union{Nothing, BNode}
    right::Union{Nothing, BNode}
end

BTree = Union{Nothing, BNode}

tree = BNode(9, BNode(4, BNode(2, nothing, nothing),
                         BNode(5, nothing, nothing)),
                BNode(12, BNode(10, nothing, nothing),
                          BNode(13, nothing, nothing)))

function count(r::BTree)
    if r == nothing
        return 0
    else
        return 1+count(r.left)+count(r.right)
    end
end

function depth(r::BTree)
    if r == nothing
        return -1
    else
        return 1 + max(depth(r.left), depth(r.right))
    end
end

function inorder(r::BTree)
    visited = Vector{Int}()
    inorder(r, visited)
    return visited
end

function inorder(r::BTree, visited::Vector{Int})
    if r == nothing
        return 
    else
        inorder(r.left, visited)
        push!(visited, r.data)
        inorder(r.right, visited)
    end
end


function left_most(r::BTree)
    d = r.data
    while r != nothing
        d = r.data
        r = r.left
    end
    return d
end

function left_most_rc(r::BTree)
    if r.left == nothing
        return r.data
    else
        return left_most_rc(r.left)
    end
end

function right_most(r::BTree)
    d = r.data
    while r != nothing
        d = r.data
        r = r.right
    end
    return d
end

function isperfect(r::BTree)
    if r == nothing
        return true
    else
        q = Queue(nothing, nothing, 0)
        push!(q, r)
        leaf_encountered = false
        while !isempty(q)
            r = pop!(q)
            if r.left == nothing 
                if r.right == nothing
                    leaf_encountered = true
                else
                    return false
                end
            else
                if r.right == nothing
                    return false
                elseif leaf_encountered 
                    return false
                else
                    push!(q, r.left)
                    push!(q, r.right)                    
                end
            end
        end
        return true
    end
end

function isbalanced(r::BTree)
    depth, balanced = isbalanced_aux(r)
    return balanced
end

function isbalanced_aux(r::BTree)
    if r == nothing
        return (-1, true)
    else
        l_depth, l_balanced = isbalanced_aux(r.left)
        r_depth, r_balanced = isbalanced_aux(r.right)
        balanced = l_balanced && r_balanced && (abs(l_depth-r_depth) <= 1)
        return (max(l_depth, r_depth)+1, balanced)
    end
end