' Binary search tree: insert, search, traversals (pre/in/post), min/max, height
#COMPILE EXE
#DIM ALL

FUNCTION PBMAIN() AS LONG
    DIM tree(1 TO 50) AS LONG
    DIM sLeft(1 TO 50) AS LONG
    DIM sRight(1 TO 50) AS LONG
    DIM vals(1 TO 9) AS LONG
    LOCAL root AS LONG
    LOCAL freeIdx AS LONG
    LOCAL i AS LONG
    LOCAL n AS LONG
    LOCAL cur AS LONG
    LOCAL node AS LONG
    LOCAL leftH AS LONG
    LOCAL rightH AS LONG
    LOCAL minNode AS LONG
    LOCAL maxNode AS LONG
    DIM istack(1 TO 50) AS LONG
    LOCAL sp AS LONG
    LOCAL value AS LONG

    vals(1) = 50
    vals(2) = 30
    vals(3) = 70
    vals(4) = 20
    vals(5) = 40
    vals(6) = 60
    vals(7) = 80
    vals(8) = 10
    vals(9) = 55

    PRINT "=== Binary Search Tree ==="
    PRINT

    root = 0
    freeIdx = 1
    FOR i = 1 TO 49
        sLeft(i) = i + 1
    NEXT i
    sLeft(50) = 0

    PRINT "Inserting values:"
    FOR n = 1 TO 9
        PRINT " " & FORMAT$(vals(n))
        value = vals(n)
        IF root = 0 THEN
            node = freeIdx
            freeIdx = sLeft(node)
            tree(node) = value
            sLeft(node) = 0
            sRight(node) = 0
            root = node
        ELSE
            node = freeIdx
            freeIdx = sLeft(node)
            tree(node) = value
            sLeft(node) = 0
            sRight(node) = 0
            cur = root
            DO
                IF value <= tree(cur) THEN
                    IF sLeft(cur) = 0 THEN
                        sLeft(cur) = node
                        EXIT DO
                    ELSE
                        cur = sLeft(cur)
                    END IF
                ELSE
                    IF sRight(cur) = 0 THEN
                        sRight(cur) = node
                        EXIT DO
                    ELSE
                        cur = sRight(cur)
                    END IF
                END IF
            LOOP
        END IF
    NEXT n
    PRINT
    PRINT
    PRINT "Tree created with 9 nodes"

    sp = 1
    istack(sp) = root
    leftH = 0
    rightH = 0
    minNode = root
    DO WHILE sLeft(minNode) <> 0
        minNode = sLeft(minNode)
    LOOP
    maxNode = root
    DO WHILE sRight(maxNode) <> 0
        maxNode = sRight(maxNode)
    LOOP
    leftH = 0
    node = root
    DO WHILE node <> 0
        leftH = leftH + 1
        node = sLeft(node)
    LOOP
    node = root
    DO WHILE node <> 0
        rightH = rightH + 1
        node = sRight(node)
    LOOP
    IF leftH > rightH THEN
        PRINT "Height: " & FORMAT$(leftH)
    ELSE
        PRINT "Height: " & FORMAT$(rightH)
    END IF
    PRINT "Min: " & FORMAT$(tree(minNode))
    PRINT "Max: " & FORMAT$(tree(maxNode))
    PRINT

    PRINT "In-order traversal:"
    sp = 0
    node = root
    DO
        DO WHILE node <> 0
            sp = sp + 1
            istack(sp) = node
            node = sLeft(node)
        LOOP
        IF sp = 0 THEN EXIT DO
        node = istack(sp)
        sp = sp - 1
        PRINT " " & FORMAT$(tree(node))
        node = sRight(node)
    LOOP
    PRINT

    PRINT "Pre-order traversal:"
    sp = 0
    IF root <> 0 THEN
        sp = sp + 1
        istack(sp) = root
    END IF
    DO
        IF sp = 0 THEN EXIT DO
        node = istack(sp)
        sp = sp - 1
        PRINT " " & FORMAT$(tree(node))
        IF sRight(node) <> 0 THEN
            sp = sp + 1
            istack(sp) = sRight(node)
        END IF
        IF sLeft(node) <> 0 THEN
            sp = sp + 1
            istack(sp) = sLeft(node)
        END IF
    LOOP
    PRINT

    PRINT "Post-order traversal:"
    DIM vst(1 TO 50) AS LONG
    sp = 0
    node = root
    DO
        DO WHILE node <> 0
            sp = sp + 1
            istack(sp) = node
            vst(sp) = 0
            node = sLeft(node)
        LOOP
        IF sp = 0 THEN EXIT DO
        node = istack(sp)
        IF vst(sp) = 0 THEN
            vst(sp) = 1
            node = sRight(node)
        ELSE
            sp = sp - 1
            PRINT " " & FORMAT$(tree(node))
            node = 0
        END IF
    LOOP
    PRINT

    PRINT "Search for 40:"
    node = root
    DO WHILE node <> 0
        IF 40 = tree(node) THEN
            PRINT "node " & FORMAT$(node)
            EXIT DO
        ELSEIF 40 < tree(node) THEN
            node = sLeft(node)
        ELSE
            node = sRight(node)
        END IF
    LOOP
    IF node = 0 THEN PRINT "  not found"

    PRINT "Search for 99:"
    node = root
    DO WHILE node <> 0
        IF 99 = tree(node) THEN
            PRINT "node " & FORMAT$(node)
            EXIT DO
        ELSEIF 99 < tree(node) THEN
            node = sLeft(node)
        ELSE
            node = sRight(node)
        END IF
    LOOP
    IF node = 0 THEN PRINT "  not found"
    PRINT

    PRINT "Binary tree tests complete."
    FUNCTION = 0
END FUNCTION
