LISP is one of the simplest computer languages in terms of syntax and semantics, and also one of the most powerful. It was developed in the mid-1950’s by John McCarthy at M.I.T. as a “LISt Processing language.” It has been historically used for virtually all Artificial Intelligence programs and is often the environment of choice for applications which require a powerful interactive working environment. LISP presents a very different way to think about programming from the “algorithmic” languages, such as Python, C++, and Java.

== Syntax ==

As its name implies, the basis of LISP is a list. One constructs a list by enumerating elements inside a pair of parentheses. For example, here is a list with four elements (the second element is also a list):

:<code>(23 (this is easy) hello 821)</code>

The elements in the list, which are not lists, are called “atoms.” For example, the atoms in the list above are: 23, ‘this, ‘hello, 821, ‘easy, and ‘is. Literals are identified with a single leading quote. Everything in LISP is either an atom or a list (but not both). The only exception is “NIL,” which is both an atom and a list. It can also be written as “()” – a pair of parentheses with nothing inside.

All statements in LISP are function calls with the following syntax: (function arg1 arg2 arg3 … argn). To evaluate a LISP statement, each of the arguments (possibly functions themselves) are evaluated, and then the function is invoked with the arguments. For example, (MULT (ADD 2 3) (ADD 1 4 2)) has a value of 35, since (ADD 2 3) has a value of 5, (ADD 1 4 2) has a value of 7, and (MULT 5 7) has a value of 35. Some functions have an arbitrary number of arguments; others require a fixed number. All statements return a value, which is either an atom or a list.

== Basic Functions (SET, SETQ, EVAL, ATOM) ==

We may assign values to variables using the function SET. For example, the statement (SET ’test 6) would have a value of a 6, and (more importantly, however) would also cause the atom ‘test to be bound to the atom 6. The function SETQ is the same as SET, but it causes LISP to act as if the first argument was quoted.
Observe the following examples:

:{| class="wikitable" style="text-align: left"
!Statement || Value || Comment
|-
|(SET ’a ( MULT 2 3))
|6
|a is an atom with a vaue of 6
|-
|(SET ’a ’(MULT 2 3))
|(MULT 2 3)
|a is a list with 3 elements
|-
|(SET ’b ’a)
|a
|b is an atom with a value of the character a
|-
|(SET ’c a)
|(MULT 2 3)
|c is a list with 3 elements
|-
|(SETQ EX (ADD 3 (MULT 2 5)))
|13
|The variable EX has a value of 13
|-
|(SETQ VOWELS ’(A E I O U))
|(A E I O U)
|VOWELS is a list of 5 elements
|}

The function EVAL returns the value of its argument, after it has been evaluated. For example, (SETQ z ’(ADD 2 3)) has a value of the list (ADD 2 3); the function (EVAL ’z) has a value of (ADD 2 3); the function (EVAL z) has a value of 5 (but the binding of the atom z has not changed). In this last example, you can think of z being “resolved” twice: once because it is an argument to a function and LISP evaluates all arguments to functions before the function is invoked, and once when the function EVAL is invoked to resolve arguments. The function ATOM can be used to determine whether an item is an atom or a list. It returns either "true", or "NIL" for false. Consider the following examples:

:{| class="wikitable" style="text-align: left"
!Statement || Value || Comment
|-
|(SETQ p '(ADD 1 2 3 4))
|(ADD 1 2 3 4)
|p is a list with 5 elements
|-
|(ATOM 'p)
|true
|The argument to ATOM is the atom p
|-
|(ATOM p)
|NIL
|Because p is not quoted, it is evaluated to the 5-element list.
|-
|(EVAL p)
|10
|The argument to EVAL is the value of p; the value of p is 10.
|}

== List Functions (CAR, CDR, CONS, REVERSE)==

The two most famous LISP functions are CAR and CDR (pronounced: could-er), named after registers of a now long-forgotten IBM machine on which LISP was first developed. The function (CAR x) returns the first item of the list x (and x must be a list or an error will occur); (CDR x) returns the list without its first element (again, x must be a list). The function CONS takes two arguments, of which the second must be a list. It returns a list which is composed by placing the first argument as the first element in the second argument’s list. The function REVERSE returns a list which is its arguments in reverse order.

The CAR and CDR functions are used extensively to grab specific elements of a list or sublist, that there's a shorthand for this: (CADR x) is the same as (CAR (CDR x)), which retrieves the second element of the list x; (CAADDAR x) is a shorthand for (CAR (CAR (CDR (CDR (CAR x))))), and so on.

The following examples illustrate the use of CAR, CDR, CONS, and REVERSE:

:{| class="wikitable" style="text-align: left"
!Statement || Value
|-
|(CAR ’(This is a list))
|This
|-
|(CDR ’(This is a list)))
|(is a list)
|-
|(CONS 'red '(white blue))
|(red white blue)
|-
|(SETQ z (CONS '(red white blue) (CDR ’(This is a list)))))
|((red white blue) is a list)
|-
|(REVERSE z)
|(list a is (red white blue))
|-
|(CDDAR z)
|(blue)
|}

== Arithmetic Functions (ADD, MULT, ...)==

As you have probably already figured out, the function ADD simply summed its arguments. We’ll also be using the following arithmetic functions:

:{| class="wikitable" style="text-align: left"
!'''Function''' || '''Result'''
|-
|(ADD x1 x2 …)
|sum of all arguments
|-
|(SUB a b)
|a-b
|-
|(MULT x1 x2 …)
|product of all arguments
|-
|(DIV a b)
|a/b
|-
|(SQUARE a)
|a*a
|-
|(EXP a n)
|an
|-
|(EQ a b)
|true if a and b are equal, NIL otherwise
|-
|(POS a)
|true if a is positive, NIL otherwise
|-
|(NEG a)
|true if a is negative, NIL otherwise
|-
|}

Functions ADD, SUB, MULT, and DIV can be written as their common mathematical symbols, +, -, *, and /. Here are some examples of these functions:

:{| class="wikitable"
!'''Statement''' || '''Value'''
|-
|(ADD (EXP 2 3) (SUB 4 1) (DIV 54 4))
|24.5
|-
|(- (* 3 2) (- 12 (+ 1 2 1)))
| -2
|-
|(ADD (SQUARE 3) (SQUARE 4))
|25
|}

== User-defined Functions ==

LISP also allows us to create our own functions using the DEF function. (We will sometimes use DEFUN rather than DEF, as it is a bit more standard terminology.) For example,
(DEF SECOND (args) (CAR (CDR args)))
defines a new function called SECOND which operates on a single parameter named “args”. SECOND will take the CDR of the parameter and then the CAR of that result. So, for example:
(SECOND ’(a b c d e))
would first CDR the list to give (b c d e), and then CAR that value returning the single character “b”. Consider the following program fragment:
:(SETQ X ’(a c s l))
:(DEF WHAT(args) (CONS args (REVERSE (CDR args))))
:(DEF SECOND(args) (CONS (CAR (CDR args)) NIL))

The following chart illustrates the use of the user-defined functions WHAT and SECOND:

:{| class="wikitable"
!Statement || Value
|-
|(WHAT X) || ((a c s l) l s c)
|-
|(SECOND X) || (c)
|-
|(SECOND (WHAT X)) || (l)
|-
|(WHAT (SECOND X)) || ((c))
|}

== Online Interpreters ==

There are many online LISP interpreters available on the Internet. The one that ACSL uses for testing its programs is CLISP that is accessible from [https://www.jdoodle.com/execute-clisp-online JDoodle]. This interpreter is nice because it is quite peppy in running programs, and functions are not case sensitive. So, <code>(CAR (CDR x))</code> is legal as is <code>(car (cdr x))</code> One drawback of this interpreter is the print function changes lowercase input into uppercase.

== Sample Problems ==

Questions from this topic will typically present a line of LISP code or a short sequence of statements and ask what is the value of the (final) statement.

=== Problem 1 ===

Evaluate the following expression. <code>(MULT (ADD 6 5 0) (MULT 5 1 2 2) (DIV 9 (SUB 2 5)))</code>

'''Solution:'''
(MULT (ADD 6 5 0) (MULT 5 1 2 2) (DIV 6 (SUB 2 5)))
(MULT 11 20 (DIV 6 -3))
(MULT 11 20 -2)
-440

=== Problem 2 ===

Evaluate the following expression: <code>(CDR ’((2 (3))(4 (5 6) 7)))</code>

'''Solution:'''
The CDR function takes the first element of its parameter (which is assumed to be a list) and returns the list with the first element removed. The first element of the list is (2 (3)) and the list without this element is
((4 (5 6) 7)), a list with one element.

=== Problem 3 ===

Consider the following program fragment:
<syntaxhighlight>
(SETQ X ’(RI VA FL CA TX))
(CAR (CDR (REVERSE X)))
</syntaxhighlight>
What is the value of the CAR expression?

'''Solution:'''
The first statement binds variable X to the list ‘(RI VA FL CA TX).
The REVERSE of this list is ‘(TX CA FL VA RI)
whose CDR is ‘(CA FL VA RI). The CAR of this list is just the atom CA (without the quote).



== Video Resources ==



The following YouTube videos show ACSL students and advisors working out some ACSL problems that have appeared in previous contests. Some of the videos contain ads; ACSL is not responsible for the ads and does not receive compensation in any form for those ads.

{|
|-
| <youtube width="300" height="180">https://youtu.be/jWFgmE279eQ</youtube>
| [https://youtu.be/jWFgmE279eQ ''LISP very gentle intro'' ('''CalculusNguyenify''')]

A very gentle introduction to the LISP category, covering the LISP syntax and the basic operators, SETQ, ADD, SUB, MULT, and DIV.

|-
| <youtube width="300" height="180">https://youtu.be/mRpbbss48sw</youtube>
| [https://youtu.be/mRpbbss48sw ''LISP Basics (for ACSL)'' ('''Tangerine Code''')]

Explains the LISP operators CAR, CDR, and REVERSE, in the context of solving an ACSL All-Star Contest problem.

|-
| <youtube width="300" height="180">https://youtu.be/50wj_f51kBM</youtube>
| [https://youtu.be/50wj_f51kBM ''LISP Basics (for ACSL)'' ('''Tangerine Code''')]

Completes the problem that was started in the above video.
|}

2018-09-12T07:29:18Z

Marc Brown:

A Finite State Automaton (FSA) is a mathematical model of computation comprising: a finite number of ''states'', of which exactly one is ''active'' at any given time; ''transition rules'' to change
the active state; an ''initial state''; and one more ''final states''. We can draw an FSA by representing each state as a circle; the final state as a double circle; the start state as the only state with an incoming arrow; and the transition rules as labeled-edges connecting the states. When labels are assigned to states, they appear inside the circle representing the state.

In this category, FSAs will be limited to parsing strings. That is, determining if a string is valid or not.

= Basics =

Here is a drawing of an FSA that is used to parse strings consists of x's and y's:

<center>
[[File:fsa.svg|250px]]
</center>

In the above FSA, there are three states: A, B, and C. The initial state is A; the final state is C. The only way to go from state A to B is by ''seeing'' the letter x. Once in state B, there are two transition rules: Seeing the letter y will cause the FSA to make C the active state, and seeing an x will keep B as the active state. State C is a final state, so if the string being parsed is completed and the FSA is in State C, the input string is said to be ''accepted'' by the FSA. In State C, seeing any additional letter y will keep the machine in state C. The FSA above will accept strings composed of one or more x’s followed by one or more y’s (e.g., xy, xxy, xxxyy, xyyy, xxyyyy).

Just like [[Boolean Algebra]] is a convenient algebraic representation of [[Digital Electronics]] Circuits, a regular expression is an algebraic representation of an FSA. For example, the regular expression corresponding to the first FSA given above is xx*yy*.

The rules for forming a regular expression (RE) are as follows:
:1. The null string (λ) is a RE.
:2. If the string a is in the input alphabet, then it is a RE.
:3. if the strings a and b are both REs, then so are the strings built up using the following rules:
::a. CONCATENATION. “ab” (a followed by b).
::b. UNION. “aUb” (a or b).
::c. CLOSURE. “a*” (a repeated zero or more times). This is known as the Kleene Star.

Identities for regular expressions appear in the next section. The order of precedence for regular expression operators is: Kleene Star, concatenation, and then union.

If we have a regular expression, then we can mechanically build an FSA to accept the strings which are generated by the regular expression. Conversely, if we have an FSA, we can mechanically develop a regular expression which will describe the strings which can be parsed by the FSA. For a given FSA or regular expression, there are many others which are equivalent to it. A “most simplified” regular expression or FSA is not always well defined.


Typical problems in the category will include: translate an FSA to a regular expression; simplify a regular expression (possibly to minimize the number of states or transitions); determine which regular expressions are equivalent; and determine which strings are accepted by either an FSA or a regular expression.

= Regular Expression Identities =

{| Class="wikitable"
|-
|1. (a*)* = a*
|-
|2. aa* = a*a
|-
|3. aa* U λ = a*
|-
|4. a(b U c) = ab U ac
|-
|5. a(ba)* = (ab)*a
|-
|6. (a U b)* = (a* U b*)*
|-
|7. (a U b)* = (a*b*)*
|-
|8. (a U b)* = a*(ba*)*
|}

= Sample Problems =

== Problem 1 ==

Find a simplified regular expression for the following FSA:

[[File:fsa_s1.png]]

'''Solution:'''

The expression 01*01 is read directly from the FSA. It is in its most simplified form.

== Problem 2 ==

Which of the following strings are accepted by the following regular expression "00*1*1U11*0*0" ?

::A. 0000001111111
::B. 1010101010
::C. 1111111
::D. 0110
::E. 10

'''Solution:'''

Choice A uses the left hand pattern (00*1*1) and choice E uses the right hand pattern (11*0*0).
Every string must start and end in the opposite digit so choices C and D don’t work. Choice B doesn’t work because all 1s and all 0s must be together.
The correct answer is A and E.

== Problem 3 ==

Which, if any, of the following Regular Expressions are equivalent?
::A. (aUb)(ab*)(b*Ua)
::B. (aab*Ubab*)a
::C. aab*Ubab*UaabaUbab*a
::D. aab*Ubab*Uaab*aUbab*a
::E. a*Ub*

'''Solution:'''

Choice B can be discarded because it is the only RE whose strings '''must''' end with an a. Choice E can be discarded since it is the only RE that can accept a null string. Choices C and D are not equal. After expanding choice A, we must compare it to choices C and D. It is equal to choice D, but not to choice C. The only REs that are equivalent are choices A and D.



= Video Resources =

Nice two-part video showing the relationship between FSAs and REs.

{|
|-
| <youtube width="300" height="180">https://youtu.be/GwsU2LPs85U</youtube>
| [https://youtu.be/GwsU2LPs85U ''1 - Convert Regular Expression to Finite-State Automaton'' ('''Barry Brown''')]

|-
| <youtube width="300" height="180">https://youtu.be/shN_kHBFOUE</youtube>
| [https://youtu.be/shN_kHBFOUE ''2 - Convert Regular Expression to Finite-State Automaton'' ('''Barry Brown''')]

This video uses the symbol "+" to mean "1 or more matches of the previous term". For example, "ab+" is the same as "abb*".
|}

File:Fsa.svg

2018-09-12T07:23:12Z

Marc Brown:

Main Page

2018-09-12T05:59:23Z

Marc Brown:

Welcome to the wiki describing the topics covered in the short programs section of the [http://www.acsl.org ACSL] contests.

If you'd like to contribute to this wiki - and we'd love to improve it - please shoot us an email requesting an account. Conversely, if we've linked to your material (especially YouTube videos) that you'd prefer that we do not reference, let us know and we will promptly remove those links.

Categories covered:

* [[Assembly Language Programming]]
* [[Bit-String Flicking]]
* [[Boolean Algebra]]
* [[Computer Number Systems]]
* [[Data Structures]]
* [[Digital Electronics]]
* [[FSAs and Regular Expressions]]
* [[Graph Theory]]
* [[LISP]]
* [[Prefix/Infix/Postfix Notation]]
* [[Recursive Functions]]
* [[What Does This Program Do?]]
* [http://www.acsl.org/categories/C1Elem-ComputerNumberSystems.pdf Elementary Division: Computer Number Systems (Contest 1)]
* [http://www.acsl.org/categories/C2Elem-Prefix-Postfix-InfixNotation.pdf Elementary Division: Prefix-Postfix-Infix Notation (Contest 2)]]
* [http://www.acsl.org/categories/C3Elem-BooleanAlgebra.pdf Elementary Division: Boolean Algebra (Contest 3)]
* [http://www.acsl.org/categories/C4Elem-GraphTheory.pdf Elementary Division: Graph Theory (Contest 4)]

== Getting started ==
* [//meta.wikimedia.org/wiki/Help:Contents User's Guide] for information on using the wiki software
* [//www.mediawiki.org/wiki/Special:MyLanguage/Manual:Configuration_settings Configuration settings list]
* [//www.mediawiki.org/wiki/Special:MyLanguage/Manual:FAQ MediaWiki FAQ]

FSAs and Regular Expressions

2018-09-12T05:58:46Z

Marc Brown: Marc Brown moved page Regular Expressions to FSAs and Regular Expressions without leaving a redirect

A Finite State Automation (FSA) has four components: an input alphabet (those letters or strings which are legal inputs); a set of transition rules to advance from state to state (given a current state and an element of the input alphabet, what is the next state); a unique start state; and one or more final states. We can draw the FSA, as shown below, by representing each state as a circular node; the final state as a double circle; the start state as the only node with an incoming arrow; and the transition rules by the strings on the edges connecting the nodes. When labels are assigned to states, they appear inside the circle representing the state.

[[File:fsa_1.png]]

If there is a path from the start state to a final state by which an input string can be parsed, then the input string is said to be “accepted” by the FSA. The FSA above will accept strings composed of one or more x’s followed by one or more y’s (e.g., xy, xxy, xxxyy, xyyy).

= Definitions =

Just like [[Boolean Algebra]] is a convenient algebraic representation of [[Digital Electronics]] Circuits, a regular expression is an algebraic representation of an FSA. For example, the regular expression corresponding to the first FSA given above is xx*yy*. The regular expression for the second FSA is extremely complex! The following simple FSAs and REs illustrate the correspondence:

{| class="wikitable" style="text-align: center"
|[[File:fsas_2-3.png|512px]]
|-
|ab*c ___________________ (aUb)c or acUbc
|}

The rules for forming a regular expression (RE) are as follows:
:1. The null string (λ) is a RE.
:2. If the string a is in the input alphabet, then it is a RE.
:3. if the strings a and b are both REs, then so are the strings built up using the following rules:
::a. CONCATENATION. “ab” (a followed by b).
::b. UNION. “aUb” (a or b).
::c. CLOSURE. “a*” (a repeated zero or more times).

If we have a regular expression, then we can mechanically build an FSA to accept the strings which are generated by the regular expression. Conversely, if we have an FSA, we can mechanically develop a regular expression which will describe the strings which can be parsed by the FSA. For a given FSA or regular expression, there are many others which are equivalent to it. A “most simplified” regular expression or FSA is not always well defined.

Identities for regular expressions appear below. The order of precedence for regular expression operators is: Kleene Star, concatenation, and then union. The Kleene Star binds from right to left; concatenation and union both bind from left to right.

Most programming languages today have a package to handle Regular Expressions in order to do pattern matching algorithms more easily. Visual BASIC has the LIKE operator that is very easy to use. We will use these “basic” symbols in our category description.

{| class="wikitable" style="text-align: left"|
|-
!Pattern
!Description
|-
|?
|Any single character
|-
|*
|Zero or more of the preceding character
|-
|#
|Any single digit
|-
|[ char-char,char,…]
|Any inclusive range or list of characters
|-
|{![charlist]}
|Any character not in a given range or list
|}

For example, the following strings either match or don’t match the pattern “[A-M][o-z][!a,e,I,o,u]?#.*”:

{| class="wikitable" style="text-align: left"|
|-
!YES
!NO
!Why not?
|-
|App$5.java
|Help1.
| E is not in the range [o-z].
|-
|Dog&2.py
|IoU$5
|There is no . at the end.
|-
|LzyG3.txt
|move6.py
|The m is not in the range [A-M].
|-
|Hot90.
|MaX7A.txt
|The A is not a digit from 0 to 9.
|}

Typical problems in the category will include: translate an FSA to a regular expression; simplify a regular expression (possibly to minimize the number of states or transitions); determine which regular expressions are equivalent; and determine which strings are accepted by either an FSA or a regular expression.

= Basic Identities =

{| Class="wikitable"
|-
|1. (a*)* = a*
|5. a(ba)* = (ab)*a
|-
|2. aa* = a*a
|6. (a U b)* = (a* U b*)*
|-
|3. aa* U λ = a*
|7. (a U b)* = (a*b*)*
|-
|4. a(b U c) = ab U ac
|8. (a U b)* = a*(ba*)*
|}

= Sample Problems =

== Sample Problem 1 ==

Find a simplified regular expression for the following FSA:

[[File:fsa_s1.png]]

'''Solution:'''

The expression 01*01 is read directly from the FSA. It is in its most simplified form.

== Sample Problem 2 ==

Which, if any, of the following Regular Expressions are equivalent?
::A. (aUb)(ab*)(b*Ua)
::B. (aab*Ubab*)a
::C. aab*Ubab*UaabaUbab*a
::D. aab*Ubab*Uaab*aUbab*a
::E. a*Ub*

'''Solution:'''

On first inspection, B can be discarded because it is the only RE whose strings must end in an a. E can also be discarded since it is the only RE that can accept a null string. C and D are not equal. After expanding A, we must compare it to C and D. It is equal to D, but not to C. A and D.

== Sample Problem 3 ==

Which of the following strings match the regular expression pattern "?[A-D]*[a-d]*#" ?

::A. 8AAAabd4
::B. MM5
::C. AAAAAAAA7
::D. Abcd9
::E. &dd88
::F. >BAD0

'''Solution:'''

The answer is A, C, D, and F. In B the character M is not in the range A-D or a-d. In E, there cannot be more than 1 digit at the end of the string. Remember that an asterisk represents 0 or more of that character or rangle of characters.

== Sample Problem 4 ==

Which of the following strings are accepted by the following regular expression "00*1*1U11*0*0" ?

::A. 0000001111111
::B. 1010101010
::C. 1111111
::D. 0110
::E. 10

'''Solution:'''

The answer is A and E. A uses the left hand pattern and E uses the right hand pattern. Every string must stat and end in the opposite digit so C and D don’t work. B doesn’t work because all 1’s and all 0’s must be together.

= Video Resources =

Nice two-part video showing the relationship between FSAs and REs.

{|
|-
| <youtube width="300" height="180">https://youtu.be/GwsU2LPs85U</youtube>
| [https://youtu.be/GwsU2LPs85U ''1 - Convert Regular Expression to Finite-State Automaton'' ('''Barry Brown''')]

| <youtube width="300" height="180">https://youtu.be/shN_kHBFOUE</youtube>
| [https://youtu.be/shN_kHBFOUE ''2 - Convert Regular Expression to Finite-State Automaton'' ('''Barry Brown''')]

This video uses the symbol "+" to mean "1 or more matches of the previous term". For example, "ab+" is the same as "abb*".
|}

2018-09-09T09:24:39Z

Marc Brown: /* Problem 3 */

At the heart of virtually every computer program are its algorithms and its data structures. It is hard to separate these two items, for data structures are meaningless without algorithms to create and manipulate them, and algorithms are usually trivial unless there are data structures on which to operate. The bigger the data sets, the more important data structures are in various algorithms.

This category concentrates on four of the most basic structures: '''stacks''', '''queues''', '''binary search trees''', and '''priority queues'''. Questions will cover these data structures and implicit algorithms, not specific to implementation language details.

A ''stack'' is usually used to save information that will need to be processed later. Items are processed in a “last-in, first-out” (LIFO) order. A ''queue'' is usually used to process items in the order in which requests are generated; a new item is not processed until all items currently on the queue are processed. This is also known as “first-in, first-out” (FIFO) order. A ''binary search tree'' is used when one is storing a set of items and needs to be able to efficiently process the operations of insertion, deletion, and query (i.e. find out if a particular item is part of the set and if not, which item in the set is close to the item in question). A ''priority queue'' is used like a binary search tree, except one cannot delete an arbitrary item, nor can one make an arbitrary query. One can only find out or delete the smallest element of the set.

There are many online resources covering these basic data structures; indeed there are many books and entire course devoted to fundamental data structures. The rest of this page is an overview of these structures.

== Stacks and Queues ==

A ''stack'' supports two operations: PUSH and POP. A command of the form “PUSH(A)” puts the key A at the top of the stack; the command “POP(X)” removes the top item from the stack and stores its value into variable X. If the stack was empty (because nothing had ever been pushed on it, or if all elements have been popped off of it), then X is given the special value of NIL. An analogy to this is a stack of books on a desk: a new book is placed on the top of the stack (pushed) and a book is removed from the top also (popped). Some textbooks call this data structure a “push-down stack” or a “LIFO stack”.

''Queues'' operate just like stacks, except items are removed from the bottom instead of the top. A good physical analogy of this is the way a train conductor or newspaper boy uses a coin machine to give change: new coins are added to the tops of the piles, and change is given from the bottom of each. Some textbooks refer to this data structure as a “FIFO stack”.

Consider the following sequence of 14 operations:

<syntaxhighlight>
PUSH(A)
PUSH(M)
PUSH(E)
POP(X)
PUSH(R)
POP(X)
PUSH(I)
POP(X)
POP(X)
POP(X)
POP(X)
PUSH(C)
PUSH(A)
PUSH(N)
</syntaxhighlight>

If these operations are applied to a stack, then the values of the pops are: E, R, I, M, A and NIL. After all of the operations, there are three items still on the stack: the N is at the top (it will be the next to be popped, if nothing else is pushed before the pop command), and C is at the bottom. If, instead of using a stack we used a queue, then the values popped would be: A, M, E, R, I and NIL. There would be three items still on the queue: N at the top and C on the bottom. Since items are removed from the bottom of a queue, C would be the next item to be popped regardless of any additional pushes. Sometimes the top and bottom of a queue are referred to as the rear and the front respectively. Therefore, items are pushed/enqueued at the rear of the queue and popped/dequeued at the front of the queue. There is a similarity to the Britsh "queueing up".

== Trees ==

''Trees'', in general, use the following terminology: the ''root'' is the top node in the tree; ''children'' are the nodes that are immediately below a ''parent'' node; ''leaves'' are the bottom-most nodes on every branch of the tree; and ''siblings'' are nodes that have the same immediate parent.

A ''binary search tree'' is composed of nodes having three parts: information (or a key), a pointer to a left child, and a pointer to a right child. It has the property that the key at every node is always greater than or equal to the key of its left child, and less than the key of its right child.

The following tree is built from the keys A, M, E, R, I, C, A, N in that order:

[[File:bst-american.svg|200px]]

The ''root'' of the resulting tree is the node containing the key A; note that duplicate keys are inserted into the tree as if they were less than their equal key. This is the ACSL convention; in some textbooks and software libraries, duplicate keys may be considered larger than their equal key. The tree has a ''depth'' (sometimes called height) of 3 because the deepest node is 3 nodes below the root. The root node has a depth of 0. Nodes with no children are called leaf nodes; there are four of them in the tree: A, C, I and N. An ''external node'' is the name given to a place where a new node could be attached to the tree. (In some textbooks, a external node is synonymous with a leaf node. ) In the final tree above, there are 9 external nodes; these are not drawn. The tree has an ''internal path length'' of 15 which is the sum of the depths of all nodes. It has an ''external path length'' of 31 which is the sum of the depths of all external nodes. To insert the N (the last key inserted), 3 ''comparisons'' were needed against the root A (>), the M (>), and the R (≤).

To perform an ''inorder'' traversal of the tree, recursively traverse the tree by first visiting the left child, then the root, then the right child. In the tree above, the nodes are visited in the following order: A, A, C, E, I, M, N, and R. A ''preorder'' travel (root, left, right) visits in the following order: A, A, M, E, C, I, R, and N. A ''postorder'' traversal (left, right, root) is: A, C, I, E, N, R, M, A. Inorder traversals are typically used to list the contents of the tree in sorted order.

Binary search trees can support the operations insert, delete, and search. Moreover, it handles the operations efficiently; in a tree with 1 million items, one can search for a particular value in about log2 1000000 ≈ 20 steps. Items can be inserted or deleted in about as many steps, too. However, binary search trees can become unbalanced, if the keys being inserted are not pretty random. For example, consider the binary search tree resulting from inserting the keys A, E, I, O, U, Y. Sophisticated techniques are available to maintain balanced trees. Binary search trees are “dynamic” data structures that can support an unlimited number of operations in any order.

To search for a node in a binary tree, the following algorithm (in pseudo-code) is used:

<syntaxhighlight>
p = root
found = FALSE
while (p ≠ NIL) and (not found)
if (x<p’s key)
p = p’s left child
else if (x>p’s key)
p = p’s right child
else
found = TRUE
end if
end while
</syntaxhighlight>

Deleting from a binary search tree is a bit more complicated. The algorithm we’ll use is as follows:

<syntaxhighlight>
p = node to delete
f = father of p
if (p has no children)
delete p
else if (p has one child)
make p’s child become f’s child
delete p
else if (p has two children)
l = p’s left child (it might also have children)
r = p’s right child (it might also have children)
make l become f’s child instead of p
stick r onto the l tree
delete p
end if
</syntaxhighlight>

These diagrams illustrate the algorithm using the tree above. At the left, we delete I (0 children); in the middle, we delete the R (1 child); and at the right, we delete the M (2 children).

{| class ="wikitable"
|[[File:bst-american-del-i.svg|200px]]
|[[File:bst-american-del-r.svg|200px]]
|[[File:bst-american-del-m.svg|200px]]
|}

There are also general trees that use the same terminology, but they have 0 or more ''subnodes'' which can be accessed with an array or linked list of pointers. ''Pre-order'' and ''post-order'' traversals are possible with these trees, but the other algorithms do not work in the same way. Applications of general trees include game theory, organizational charts, family trees, etc.

''Balanced'' trees minimize searching time when every leaf node has a depth of within 1 of every other leaf node. ''Complete'' trees are filled in at every level and are always balanced. ''Strictly binary'' trees ensure that every node has either 0 or 2 subnodes. You may want to consider how there are exactly 5 strictly binary trees with 7 nodes.

== Priority Queues ==

A ''priority queue'' is quite similar to a binary search tree, but one can only delete the smallest item and retrieve for the smallest. These insert and delete operations can be done in a guaranteed time proportional to the log of the number of items; the retrieve-the-smallest can be done in constant time.

The standard way to implement a priority queue is using a ''heap'' data structure. A heap uses a binary tree (that is, a tree with two children) and maintains the following two properties: every node is smaller than its two children (nothing is said about the relative magnitude of the two children), and the resulting tree contains no “holes”. That is, all levels of the tree are completely filled, except the bottom level, which is filled in from the left to the right.

The algorithm for insertion is not too difficult: put the new node at the bottom of the tree and then go up the tree, making exchanges with its parent, until the tree is valid.

The heap at the left
was building from the letters A, M, E, R, I, C, A, N (in that order); the heap at the right is after a C has been added.

{| class="wikitable"
|[[File:heap-american.svg|220px]]||
[[File:heap-american-insert-c.svg|220px]]
|}

The smallest value is always the root. To delete it (and one can only delete the smallest value), one replaces it with the bottom-most and right-most element, and then walks down the tree making exchanges with the child in order to insure that the tree is valid. The following pseudo-code formalizes this notion:

<syntaxhighlight>
b = bottom-most and right-most element
p = root of tree
p’s key = b’s key
delete b
while (p is larger than either child)
exchange p with smaller child
p = smaller child
end while
</syntaxhighlight>

When the smallest item is at the root of the heap, the heap is called a ''min-heap''. Of course, ''max-heaps'' are also possible and are common in practice. An efficient implementation of a heap uses an array, rather than a tree data structure.

== Sample Problems ==

=== Problem 1 ===

Consider an initially empty stack. What is the value of Z when these operations are performed:

<syntaxhighlight>
PUSH(3)
PUSH(6)
PUSH(8)
POP(Y)
POP(X)
PUSH(X-Y)
POP(Z)
</syntaxhighlight>

'''Solution:''' The first POP(Y) stores 8 in Y. The POP(X) stores 6 in X. Then, 8-6=2 is pushed onto the stack. Finally, POP(Z) removes the 2 and stores it in Z.

=== Problem 2 ===

Create a min-heap with the letters in the word PROGRAMMING. What are the letters in the bottom-most row, from left to right?

'''Solution:''' The bottom row contains the letters RORN, from left-to-right. Here is the entire heap:
[[File:heap-programming.svg|200px]]

=== Problem 3 ===

Create a binary search tree from the letters in the word PROGRAM. What is the internal path length?

Solution: When drawing the tree, P has a depth of 0, O and R have a depth of 1, G and R have a depth of 2, and A and M have a depth of 3. Therefore, the internal path length is 12. Here is the tree:

[[File:bst-program.svg|200px]]

= Video Resources =

== ACSL Videos ==

The following YouTube videos show ACSL students and advisors working out some ACSL problems that have appeared in previous contests. Some of the videos contain ads; ACSL is not responsible for the ads and does not receive compensation in any form for those ads.


{|
|-
| <youtube width="300" height="180">https://youtu.be/gXj7K_petqo</youtube>
| [https://youtu.be/gXj7K_petqo ''Data Structures (Stacks and Queues)'' ('''Tangerine Code''')]

A general tutorial on stacks and queues.

|-
| <youtube width="300" height="180">https://youtu.be/_BnbbOhyroQ</youtube>
| [https://youtu.be/_BnbbOhyroQ ''Construct a Binary Search Tree'' ('''Tangerine Code''')]

Shows how to build a binary search tree from the letters '''S U S H I'''.
|-
| <youtube width="300" height="180">https://youtu.be/l9aMO7lgHj0</youtube>
| [https://youtu.be/l9aMO7lgHj0 ''Binary Search Tree ACSL Problem (Internal Path Length)'' ('''Tangerine Code''')]

A general tutorial on internal path length of a binary search tree
|}

== Other Videos ==

There is no shortage of instructional video material covering basic data structures. Here is a series that combines teaching concepts with showing Java code that implements the concepts. Most of the ACSL questions will not involve coding the basic operations on the data structures; rather, the problems will involve high-level understanding of them. However, seeing the code is an excellent way to thoroughly understand these data structures, and what it takes to implement them.
{|
|-
| <youtube width="300" height="180">https://youtu.be/wjI1WNcIntg</youtube>
| [https://youtu.be/wjI1WNcIntg ''Data Structures: Stacks and Queues'' ('''HackerRank''')]

The first half of the video is a nice description of stacks and queues; the second half walks through very clean Java code that implements the fundamental methods on these data structures.
|-
| <youtube width="300" height="180">https://youtu.be/njTh_OwMljA</youtube>
| [https://youtu.be/njTh_OwMljA ''Data Structures: Linked Lists'' ('''HackerRank''')]

Although ACSL does not cover linked lists per se, they are a great preliminary study for binary search trees.
|-
| <youtube width="300" height="180">https://youtu.be/oSWTXtMglKE</youtube>
| [https://youtu.be/oSWTXtMglKE ''Data Structures: Trees'' ('''HackerRank''')]

Learn about binary search trees. This video is a part of HackerRank's ''Cracking The Coding Interview Tutorial''with Gayle Laakmann McDowell. The first half of the video is an clear and eloquent description of binary search trees; the second half walks through very clean Java code that implements the fundamental methods.
|-
| <youtube width="300" height="180">https://youtu.be/t0Cq6tVNRBA</youtube>
| [https://youtu.be/t0Cq6tVNRBA ''Data Structures: Heaps'' ('''HackerRank''')]

Learn about heaps. This video is a part of HackerRank's ''Cracking The Coding Interview Tutorial'' with Gayle Laakmann McDowell. The first half of the video is an clear and eloquent description of heaps; the second half walks through very clean Java code that implements the fundamental methods.
|}

Here are a few more videos covering the basics of binary search trees.

{|
|-
| <youtube width="300" height="180">https://youtu.be/FvdPo8PBQtc</youtube>
| [https://youtu.be/FvdPo8PBQtc ''How to Construct a Binary Search Tree'' ('''edutechional''')]

''In this algorithm tutorial, I walk through how to construct a binary search tree given an unordered array, and then how to find elements inside of the tree.''
|}

File:Bst-program.svg

2018-09-09T09:24:18Z

Marc Brown:

Data Structures

2018-09-09T09:13:16Z

Marc Brown: /* Other Videos */

At the heart of virtually every computer program are its algorithms and its data structures. It is hard to separate these two items, for data structures are meaningless without algorithms to create and manipulate them, and algorithms are usually trivial unless there are data structures on which to operate. The bigger the data sets, the more important data structures are in various algorithms.

This category concentrates on four of the most basic structures: '''stacks''', '''queues''', '''binary search trees''', and '''priority queues'''. Questions will cover these data structures and implicit algorithms, not specific to implementation language details.

A ''stack'' is usually used to save information that will need to be processed later. Items are processed in a “last-in, first-out” (LIFO) order. A ''queue'' is usually used to process items in the order in which requests are generated; a new item is not processed until all items currently on the queue are processed. This is also known as “first-in, first-out” (FIFO) order. A ''binary search tree'' is used when one is storing a set of items and needs to be able to efficiently process the operations of insertion, deletion, and query (i.e. find out if a particular item is part of the set and if not, which item in the set is close to the item in question). A ''priority queue'' is used like a binary search tree, except one cannot delete an arbitrary item, nor can one make an arbitrary query. One can only find out or delete the smallest element of the set.

There are many online resources covering these basic data structures; indeed there are many books and entire course devoted to fundamental data structures. The rest of this page is an overview of these structures.

== Stacks and Queues ==

A ''stack'' supports two operations: PUSH and POP. A command of the form “PUSH(A)” puts the key A at the top of the stack; the command “POP(X)” removes the top item from the stack and stores its value into variable X. If the stack was empty (because nothing had ever been pushed on it, or if all elements have been popped off of it), then X is given the special value of NIL. An analogy to this is a stack of books on a desk: a new book is placed on the top of the stack (pushed) and a book is removed from the top also (popped). Some textbooks call this data structure a “push-down stack” or a “LIFO stack”.

''Queues'' operate just like stacks, except items are removed from the bottom instead of the top. A good physical analogy of this is the way a train conductor or newspaper boy uses a coin machine to give change: new coins are added to the tops of the piles, and change is given from the bottom of each. Some textbooks refer to this data structure as a “FIFO stack”.

Consider the following sequence of 14 operations:

<syntaxhighlight>
PUSH(A)
PUSH(M)
PUSH(E)
POP(X)
PUSH(R)
POP(X)
PUSH(I)
POP(X)
POP(X)
POP(X)
POP(X)
PUSH(C)
PUSH(A)
PUSH(N)
</syntaxhighlight>

If these operations are applied to a stack, then the values of the pops are: E, R, I, M, A and NIL. After all of the operations, there are three items still on the stack: the N is at the top (it will be the next to be popped, if nothing else is pushed before the pop command), and C is at the bottom. If, instead of using a stack we used a queue, then the values popped would be: A, M, E, R, I and NIL. There would be three items still on the queue: N at the top and C on the bottom. Since items are removed from the bottom of a queue, C would be the next item to be popped regardless of any additional pushes. Sometimes the top and bottom of a queue are referred to as the rear and the front respectively. Therefore, items are pushed/enqueued at the rear of the queue and popped/dequeued at the front of the queue. There is a similarity to the Britsh "queueing up".

== Trees ==

''Trees'', in general, use the following terminology: the ''root'' is the top node in the tree; ''children'' are the nodes that are immediately below a ''parent'' node; ''leaves'' are the bottom-most nodes on every branch of the tree; and ''siblings'' are nodes that have the same immediate parent.

A ''binary search tree'' is composed of nodes having three parts: information (or a key), a pointer to a left child, and a pointer to a right child. It has the property that the key at every node is always greater than or equal to the key of its left child, and less than the key of its right child.

The following tree is built from the keys A, M, E, R, I, C, A, N in that order:

[[File:bst-american.svg|200px]]

The ''root'' of the resulting tree is the node containing the key A; note that duplicate keys are inserted into the tree as if they were less than their equal key. This is the ACSL convention; in some textbooks and software libraries, duplicate keys may be considered larger than their equal key. The tree has a ''depth'' (sometimes called height) of 3 because the deepest node is 3 nodes below the root. The root node has a depth of 0. Nodes with no children are called leaf nodes; there are four of them in the tree: A, C, I and N. An ''external node'' is the name given to a place where a new node could be attached to the tree. (In some textbooks, a external node is synonymous with a leaf node. ) In the final tree above, there are 9 external nodes; these are not drawn. The tree has an ''internal path length'' of 15 which is the sum of the depths of all nodes. It has an ''external path length'' of 31 which is the sum of the depths of all external nodes. To insert the N (the last key inserted), 3 ''comparisons'' were needed against the root A (>), the M (>), and the R (≤).

To perform an ''inorder'' traversal of the tree, recursively traverse the tree by first visiting the left child, then the root, then the right child. In the tree above, the nodes are visited in the following order: A, A, C, E, I, M, N, and R. A ''preorder'' travel (root, left, right) visits in the following order: A, A, M, E, C, I, R, and N. A ''postorder'' traversal (left, right, root) is: A, C, I, E, N, R, M, A. Inorder traversals are typically used to list the contents of the tree in sorted order.

Binary search trees can support the operations insert, delete, and search. Moreover, it handles the operations efficiently; in a tree with 1 million items, one can search for a particular value in about log2 1000000 ≈ 20 steps. Items can be inserted or deleted in about as many steps, too. However, binary search trees can become unbalanced, if the keys being inserted are not pretty random. For example, consider the binary search tree resulting from inserting the keys A, E, I, O, U, Y. Sophisticated techniques are available to maintain balanced trees. Binary search trees are “dynamic” data structures that can support an unlimited number of operations in any order.

To search for a node in a binary tree, the following algorithm (in pseudo-code) is used:

<syntaxhighlight>
p = root
found = FALSE
while (p ≠ NIL) and (not found)
if (x<p’s key)
p = p’s left child
else if (x>p’s key)
p = p’s right child
else
found = TRUE
end if
end while
</syntaxhighlight>

Deleting from a binary search tree is a bit more complicated. The algorithm we’ll use is as follows:

<syntaxhighlight>
p = node to delete
f = father of p
if (p has no children)
delete p
else if (p has one child)
make p’s child become f’s child
delete p
else if (p has two children)
l = p’s left child (it might also have children)
r = p’s right child (it might also have children)
make l become f’s child instead of p
stick r onto the l tree
delete p
end if
</syntaxhighlight>

These diagrams illustrate the algorithm using the tree above. At the left, we delete I (0 children); in the middle, we delete the R (1 child); and at the right, we delete the M (2 children).

{| class ="wikitable"
|[[File:bst-american-del-i.svg|200px]]
|[[File:bst-american-del-r.svg|200px]]
|[[File:bst-american-del-m.svg|200px]]
|}

There are also general trees that use the same terminology, but they have 0 or more ''subnodes'' which can be accessed with an array or linked list of pointers. ''Pre-order'' and ''post-order'' traversals are possible with these trees, but the other algorithms do not work in the same way. Applications of general trees include game theory, organizational charts, family trees, etc.

''Balanced'' trees minimize searching time when every leaf node has a depth of within 1 of every other leaf node. ''Complete'' trees are filled in at every level and are always balanced. ''Strictly binary'' trees ensure that every node has either 0 or 2 subnodes. You may want to consider how there are exactly 5 strictly binary trees with 7 nodes.

== Priority Queues ==

A ''priority queue'' is quite similar to a binary search tree, but one can only delete the smallest item and retrieve for the smallest. These insert and delete operations can be done in a guaranteed time proportional to the log of the number of items; the retrieve-the-smallest can be done in constant time.

The standard way to implement a priority queue is using a ''heap'' data structure. A heap uses a binary tree (that is, a tree with two children) and maintains the following two properties: every node is smaller than its two children (nothing is said about the relative magnitude of the two children), and the resulting tree contains no “holes”. That is, all levels of the tree are completely filled, except the bottom level, which is filled in from the left to the right.

The algorithm for insertion is not too difficult: put the new node at the bottom of the tree and then go up the tree, making exchanges with its parent, until the tree is valid.

The heap at the left
was building from the letters A, M, E, R, I, C, A, N (in that order); the heap at the right is after a C has been added.

{| class="wikitable"
|[[File:heap-american.svg|220px]]||
[[File:heap-american-insert-c.svg|220px]]
|}

The smallest value is always the root. To delete it (and one can only delete the smallest value), one replaces it with the bottom-most and right-most element, and then walks down the tree making exchanges with the child in order to insure that the tree is valid. The following pseudo-code formalizes this notion:

<syntaxhighlight>
b = bottom-most and right-most element
p = root of tree
p’s key = b’s key
delete b
while (p is larger than either child)
exchange p with smaller child
p = smaller child
end while
</syntaxhighlight>

When the smallest item is at the root of the heap, the heap is called a ''min-heap''. Of course, ''max-heaps'' are also possible and are common in practice. An efficient implementation of a heap uses an array, rather than a tree data structure.

== Sample Problems ==

=== Problem 1 ===

Consider an initially empty stack. What is the value of Z when these operations are performed:

<syntaxhighlight>
PUSH(3)
PUSH(6)
PUSH(8)
POP(Y)
POP(X)
PUSH(X-Y)
POP(Z)
</syntaxhighlight>

'''Solution:''' The first POP(Y) stores 8 in Y. The POP(X) stores 6 in X. Then, 8-6=2 is pushed onto the stack. Finally, POP(Z) removes the 2 and stores it in Z.

=== Problem 2 ===

Create a min-heap with the letters in the word PROGRAMMING. What are the letters in the bottom-most row, from left to right?

'''Solution:''' The bottom row contains the letters RORN, from left-to-right. Here is the entire heap:
[[File:heap-programming.svg|200px]]

=== Problem 3 ===

Create a binary search tree from the letters in the word PROGRAMMING. What is the internal path length?

Solution: When drawing the tree, P has a depth of 0, O and R have a depth of 1, G and R have a depth of 2, A and M have a depth of 3, M and N have a depth of 4, I has a depth of 5, and G has a depth of 6. Therefore, the internal path length is 31.

= Video Resources =

== ACSL Videos ==

The following YouTube videos show ACSL students and advisors working out some ACSL problems that have appeared in previous contests. Some of the videos contain ads; ACSL is not responsible for the ads and does not receive compensation in any form for those ads.


{|
|-
| <youtube width="300" height="180">https://youtu.be/gXj7K_petqo</youtube>
| [https://youtu.be/gXj7K_petqo ''Data Structures (Stacks and Queues)'' ('''Tangerine Code''')]

A general tutorial on stacks and queues.

|-
| <youtube width="300" height="180">https://youtu.be/_BnbbOhyroQ</youtube>
| [https://youtu.be/_BnbbOhyroQ ''Construct a Binary Search Tree'' ('''Tangerine Code''')]

Shows how to build a binary search tree from the letters '''S U S H I'''.
|-
| <youtube width="300" height="180">https://youtu.be/l9aMO7lgHj0</youtube>
| [https://youtu.be/l9aMO7lgHj0 ''Binary Search Tree ACSL Problem (Internal Path Length)'' ('''Tangerine Code''')]

A general tutorial on internal path length of a binary search tree
|}

== Other Videos ==

There is no shortage of instructional video material covering basic data structures. Here is a series that combines teaching concepts with showing Java code that implements the concepts. Most of the ACSL questions will not involve coding the basic operations on the data structures; rather, the problems will involve high-level understanding of them. However, seeing the code is an excellent way to thoroughly understand these data structures, and what it takes to implement them.
{|
|-
| <youtube width="300" height="180">https://youtu.be/wjI1WNcIntg</youtube>
| [https://youtu.be/wjI1WNcIntg ''Data Structures: Stacks and Queues'' ('''HackerRank''')]

The first half of the video is a nice description of stacks and queues; the second half walks through very clean Java code that implements the fundamental methods on these data structures.
|-
| <youtube width="300" height="180">https://youtu.be/njTh_OwMljA</youtube>
| [https://youtu.be/njTh_OwMljA ''Data Structures: Linked Lists'' ('''HackerRank''')]

Although ACSL does not cover linked lists per se, they are a great preliminary study for binary search trees.
|-
| <youtube width="300" height="180">https://youtu.be/oSWTXtMglKE</youtube>
| [https://youtu.be/oSWTXtMglKE ''Data Structures: Trees'' ('''HackerRank''')]

Learn about binary search trees. This video is a part of HackerRank's ''Cracking The Coding Interview Tutorial''with Gayle Laakmann McDowell. The first half of the video is an clear and eloquent description of binary search trees; the second half walks through very clean Java code that implements the fundamental methods.
|-
| <youtube width="300" height="180">https://youtu.be/t0Cq6tVNRBA</youtube>
| [https://youtu.be/t0Cq6tVNRBA ''Data Structures: Heaps'' ('''HackerRank''')]

Learn about heaps. This video is a part of HackerRank's ''Cracking The Coding Interview Tutorial'' with Gayle Laakmann McDowell. The first half of the video is an clear and eloquent description of heaps; the second half walks through very clean Java code that implements the fundamental methods.
|}

Here are a few more videos covering the basics of binary search trees.

{|
|-
| <youtube width="300" height="180">https://youtu.be/FvdPo8PBQtc</youtube>
| [https://youtu.be/FvdPo8PBQtc ''How to Construct a Binary Search Tree'' ('''edutechional''')]

''In this algorithm tutorial, I walk through how to construct a binary search tree given an unordered array, and then how to find elements inside of the tree.''
|}