; ------------------------------------------------------------------------
; A Binary Tree example.
;
; The Tree is saved in a global pointer - Tree.
; Only insert and preorder, inorder & postorder functions are implemented.
; ------------------------------------------------------------------------

        format PE console

        include 'macro\import32.inc'

        section '.code' code readable executable
start:
; ------------------------------------------------------
; First insert ten random integers into our Binary Tree.
; ------------------------------------------------------
        mov ebx, 10
.insert_items:
        call dword [rand]
        and eax, 0xff
        push eax
        push tree
        call insert
        dec ebx
        jnz .insert_items
; ----------------------------------------------------------
; Now just do traversals of the Tree and print the integers.
; ----------------------------------------------------------

; PRE-ORDER
        push pre_msg
        call dword [printf]
        add esp, 4
        push dword [tree]
        call preorder

; IN-ORDER
        push in_msg
        call dword [printf]
        add esp, 4
        push dword [tree]
        call inorder

; POST-ORDER
        push post_msg
        call dword [printf]
        add esp, 4
        push dword [tree]
        call postorder

        push thanks
        call dword [printf]
        add esp, 4
        call dword [getchar]
; ----------------------
; End of the show. Exit!
; ----------------------
        push 0
        call dword [exit]

; ----------------------------------------------------------------
; Insert the item given in the Tree pointed by the address passed.
; Insert works in such a way that the  inorder traversal will give
; us results in non-decreasing sorted order.
; ----------------------------------------------------------------
insert:
root equ ebp+8
item equ ebp+12
        enter 0,0
        mov eax, [root]
        cmp dword [eax], 0
        jz .new_node
        mov ecx, [eax]
        mov edx, [item]
        cmp [ecx], edx
        jle .insert_right
; Otherwise insert left.
        add ecx, 4
.recursion:
        push edx
        push ecx
        call insert
        jmp .return
.insert_right:
        add ecx, 8
        jmp .recursion
.new_node:
        push 12
        call dword [malloc]
        add esp, 4
        mov ecx, [root]
        mov [ecx], eax
        mov edx, [item]
        mov [eax], edx
        mov dword [eax+4], 0
        mov dword [eax+8], 0
.return:
        leave
        ret 8

; -------------------------------------------------
; Travers the Tree in preorder and print each item.
; -------------------------------------------------
preorder:
root equ ebp+8

        enter 0,0
        cmp dword [root], 0
        jz .return

        mov eax, [root]
        push dword [eax]
        push str1
        call dword [printf]
        add esp, 8

        mov eax, [root]
        add eax, 4
        push dword [eax]
        call inorder

        mov eax, [root]
        add eax, 8
        push dword [eax]
        call inorder
.return:
        leave
        ret 4

; ------------------------------------------------
; Travers the Tree in inorder and print each item.
; ------------------------------------------------
inorder:
root equ ebp+8

        enter 0,0
        cmp dword [root], 0
        jz .return

        mov eax, [root]
        add eax, 4
        push dword [eax]
        call inorder

        mov eax, [root]
        push dword [eax]
        push str1
        call dword [printf]
        add esp, 8

        mov eax, [root]
        add eax, 8
        push dword [eax]
        call inorder
.return:
        leave
        ret 4


; ------------------------------------------------
; Travers the Tree in postorder and print each item.
; ------------------------------------------------
postorder:
root equ ebp+8

        enter 0,0
        cmp dword [root], 0
        jz .return

        mov eax, [root]
        add eax, 4
        push dword [eax]
        call inorder

        mov eax, [root]
        add eax, 8
        push dword [eax]
        call inorder

        mov eax, [root]
        push dword [eax]
        push str1
        call dword [printf]
        add esp, 8
.return:
        leave
        ret 4


        section '.data' data readable writable
NL equ 13,10
tree dd 0
pre_msg db NL,'Preorder Traversal: ',0
in_msg  db NL,'Inorder Traversal: ',0
post_msg db NL,'Postorder Traversal: ',0
thanks db NL,NL,'Thanks for watching this boring stuff.',NL,NL,'Now press <ENTER> to exit ',0
str1 db "%d ",0


        section '.idata' import data readable

library msvcrt,'msvcrt.dll'

import  msvcrt,\
        exit,'exit',\
        rand,'rand',\
        malloc,'malloc',\
        printf,'printf',\
        getchar,'getchar'