pseudo-1-dsa

struct node
    declare data: integer
    declare next: pointer of type node
end struct

begin procedure newNode
    pass in: integer val
    initialize pointer temp of type node and allocate memory to it
    temp→data ← val
    temp→left_child ← NULL
    temp→right_child ← NULL
    pass out pointer temp of type node
end procedure

begin procedure insert
    pass in: pointer root of type node, integer data
    if root is equal to NULL
        return call newNode(data)
    end if
    if data is less than root→data
        root→left_child ← call insert(root→left_child, data)
    else
        root→right_child ← call insert(root→right_child, data)
    end if
    pass out: pointer root of type node
end procedure

begin procedure minValueNode
    pass in: pointer root of type node
    initialize pointer current of type node as root
    while current and current→left_child is not equal to NULL do
        current ← current→left_child
    end do
    pass out: pointer root of type node
end procedure

begin procedure deleteNode
    pass in: pointer root of type node, integer data
    if root is equal to NULL
        return root
    end if
    if data is less than root→data
        root→left_child ← call deleteNode(root→left_child, data)
    else if data is greater than root→data
        root→right_child ← call deleteNode(root→right_child, data)
    else
        if root→left_child is equal to NULL
            initialize pointer temp of type node as root→right_child
            free the pointer root
            return temp
        else if root→right_child is equal to NULL
            initialize pointer temp of type node as root→left_child
            free the pointer root
            return temp
        end if
        initialize pointer temp of type node as call minValueNode(root→right_child)
        root→data ← temp→data
        root→right_child ← call deleteNode(root→right_child, temp→data)
    end if
    pass out: pointer root of type node
end procedure

begin procedure height
    pass in: pointer root of type node
    if root is equal to NULL
        return NULL
    else
        initialize lheight as call height(root→left_child)
        initialize rheight as call height(root→right_child)
        if lheight is greater than rheight
            return (lheight+1)
        else
            return (rheight+1)
        end if
    end if
end procedure

begin procedure printGivenLevel
    pass in: pointer root of type node, integer level
    if root is equal to NULL
        return NULL
    end if
    if level is equal to 1
        print root→data
    else if level is greater than 1
        call printGivenLevel(root→left_child, level-1)
        call printGivenLevel(root→right_child, level-1)
    end if
    pass out: NULL
end procedure

begin procedure printLevelOrder
    pass in: pointer root of type node
    initialize integer h as call height(root)
    for i from 1 to h do
        call printGivenLevel(root, i)
    end do
    pass out: NULL
end procedure

begin procedure printPreOrder
    pass in: pointer root of type node
    if root is not equal to NULL
        print root→data
        call printPreOrder(root→left_child)
        call printPreOrder(root→right_child)
    end if
    pass out: NULL
end procedure

begin procedure printInOrder
    pass in: pointer root of type node
    if root is not equal to NULL
        call printInOrder(root→left_child)
        print root→data
        call printInOrder(root→right_child)
    end if
    pass out: NULL
end procedure

begin procedure printPostOrder
    pass in: pointer root of type node
    if root is not equal to NULL
        call printPostOrder(root→left_child)
        call printPostOrder(root→right_child)
        print root→data
    end if
    pass out: NULL
end procedure