' Binary Search Tree — tree operations using parallel arrays
#COMPILE EXE
#DIM ALL

FUNCTION PBMAIN() AS LONG
    LOCAL keys(1000) AS LONG
    LOCAL leftChild(1000) AS LONG
    LOCAL rightChild(1000) AS LONG
    LOCAL nodeCount AS LONG
    LOCAL root AS LONG
    LOCAL i AS LONG
    LOCAL j AS LONG
    LOCAL keyVal AS LONG
    LOCAL current AS LONG
    LOCAL parent AS LONG
    LOCAL dir AS LONG
    LOCAL found AS LONG
    LOCAL searchKey AS LONG
    LOCAL insertErrors AS LONG
    LOCAL testCount AS LONG
    LOCAL passCount AS LONG
    LOCAL failCount AS LONG
    LOCAL inorder(1000) AS LONG
    LOCAL inorderCount AS LONG
    LOCAL stack(1000) AS LONG
    LOCAL stackSize AS LONG
    LOCAL lineStr AS STRING
    LOCAL elemStr AS STRING
    testCount = 0
    passCount = 0
    failCount = 0
    insertErrors = 0
    PRINT "============================================"
    PRINT "       BINARY SEARCH TREE"
    PRINT "============================================"
    PRINT ""
    nodeCount = 0
    root = -1
    PRINT "Inserting values:"
    PRINT ""
    FOR i = 0 TO 19
        keyVal = (i * 17 + 5) MOD 50
        PRINT " Insert " + STR$(keyVal)
        IF nodeCount = 0 THEN
            keys(0) = keyVal
            leftChild(0) = -1
            rightChild(0) = -1
            root = 0
            nodeCount = 1
        ELSE
            current = root
            parent = -1
            dir = 0
            DO WHILE current <> -1
                parent = current
                IF keyVal < keys(current) THEN
                    current = leftChild(current)
                    dir = 0
                ELSE
                    IF keyVal > keys(current) THEN
                        current = rightChild(current)
                        dir = 1
                    ELSE
                        EXIT DO
                    END IF
                END IF
            LOOP
            IF current = -1 THEN
                keys(nodeCount) = keyVal
                leftChild(nodeCount) = -1
                rightChild(nodeCount) = -1
                IF dir = 0 THEN
                    leftChild(parent) = nodeCount
                ELSE
                    rightChild(parent) = nodeCount
                END IF
                nodeCount = nodeCount + 1
            END IF
        END IF
    NEXT i
    PRINT ""
    PRINT "Tree has " + STR$(nodeCount) + " nodes"
    PRINT ""
    inorderCount = 0
    stackSize = 0
    current = root
    DO WHILE current <> -1 OR stackSize > 0
        DO WHILE current <> -1
            stack(stackSize) = current
            stackSize = stackSize + 1
            current = leftChild(current)
        LOOP
        IF stackSize > 0 THEN
            stackSize = stackSize - 1
            current = stack(stackSize)
            inorder(inorderCount) = keys(current)
            inorderCount = inorderCount + 1
            current = rightChild(current)
        END IF
    LOOP
    PRINT "In-order traversal:"
    lineStr = ""
    FOR i = 0 TO inorderCount - 1
        elemStr = STR$(inorder(i))
        DO WHILE LEN(elemStr) < 3
            elemStr = " " + elemStr
        LOOP
        lineStr = lineStr + elemStr + " "
    NEXT i
    PRINT lineStr
    PRINT ""
    testCount = testCount + 1
    insertErrors = 0
    FOR i = 1 TO inorderCount - 1
        IF inorder(i) < inorder(i - 1) THEN
            insertErrors = insertErrors + 1
        END IF
    NEXT i
    IF insertErrors = 0 THEN
        passCount = passCount + 1
        PRINT "PASS: In-order correctly sorted"
    ELSE
        failCount = failCount + 1
        PRINT "FAIL: " + STR$(insertErrors) + " ordering errors"
    END IF
    PRINT ""
    PRINT "============================================"
    PRINT "     SEARCH OPERATIONS"
    PRINT "============================================"
    PRINT ""
    FOR searchKey = 0 TO 49
        current = root
        found = 0
        DO WHILE current <> -1
            IF searchKey = keys(current) THEN
                found = 1
                EXIT DO
            ELSE
                IF searchKey < keys(current) THEN
                    current = leftChild(current)
                ELSE
                    current = rightChild(current)
                END IF
            END IF
        LOOP
        testCount = testCount + 1
        IF found = 1 THEN
            passCount = passCount + 1
        END IF
    NEXT searchKey
    PRINT "Search verification complete"
    PRINT ""
    PRINT "============================================"
    PRINT "     MIN AND MAX"
    PRINT "============================================"
    PRINT ""
    current = root
    DO WHILE leftChild(current) <> -1
        current = leftChild(current)
    LOOP
    PRINT "Minimum value: " + STR$(keys(current))
    testCount = testCount + 1
    IF keys(current) = 0 OR keys(current) = 1 THEN
        passCount = passCount + 1
    ELSE
        failCount = failCount + 1
    END IF
    current = root
    DO WHILE rightChild(current) <> -1
        current = rightChild(current)
    LOOP
    PRINT "Maximum value: " + STR$(keys(current))
    PRINT ""
    PRINT "============================================"
    PRINT "     PREDECESSOR AND SUCCESSOR"
    PRINT "============================================"
    PRINT ""
    LOCAL targetKey AS LONG
    LOCAL pred AS LONG
    LOCAL succ AS LONG
    targetKey = 25
    current = root
    pred = -1
    succ = -1
    DO WHILE current <> -1
        IF keys(current) = targetKey THEN
            IF leftChild(current) <> -1 THEN
                pred = leftChild(current)
                DO WHILE rightChild(pred) <> -1
                    pred = rightChild(pred)
                LOOP
            END IF
            IF rightChild(current) <> -1 THEN
                succ = rightChild(current)
                DO WHILE leftChild(succ) <> -1
                    succ = leftChild(succ)
                LOOP
            END IF
            EXIT DO
        ELSE
            IF targetKey < keys(current) THEN
                IF rightChild(current) <> -1 THEN
                    IF keys(current) < keys(rightChild(current)) THEN
                        succ = current
                    END IF
                END IF
                current = leftChild(current)
            ELSE
                IF leftChild(current) <> -1 THEN
                    IF keys(current) > keys(leftChild(current)) THEN
                        pred = current
                    END IF
                END IF
                current = rightChild(current)
            END IF
        END IF
    LOOP
    IF pred <> -1 THEN
        PRINT "Predecessor of " + STR$(targetKey) + ": " + STR$(keys(pred))
    ELSE
        PRINT "No predecessor for " + STR$(targetKey)
    END IF
    IF succ <> -1 THEN
        PRINT "Successor of " + STR$(targetKey) + ": " + STR$(keys(succ))
    ELSE
        PRINT "No successor for " + STR$(targetKey)
    END IF
    PRINT ""
    PRINT "============================================"
    PRINT "     TREE HEIGHT"
    PRINT "============================================"
    PRINT ""
    LOCAL heights(1000) AS LONG
    LOCAL maxHeight AS LONG
    LOCAL hLeft AS LONG
    LOCAL hRight AS LONG
    FOR i = nodeCount - 1 TO 0 STEP -1
        hLeft = 0
        hRight = 0
        IF leftChild(i) <> -1 THEN
            hLeft = heights(leftChild(i)) + 1
        END IF
        IF rightChild(i) <> -1 THEN
            hRight = heights(rightChild(i)) + 1
        END IF
        IF hLeft > hRight THEN
            heights(i) = hLeft
        ELSE
            heights(i) = hRight
        END IF
    NEXT i
    IF root <> -1 THEN
        maxHeight = heights(root)
    ELSE
        maxHeight = 0
    END IF
    PRINT "Tree height: " + STR$(maxHeight)
    PRINT ""
    PRINT "Results: " + STR$(passCount) + " passed, " + STR$(failCount) + " failed of " + STR$(testCount)
    FUNCTION = 0
END FUNCTION
