By Harmanraj Singh Wadhwa (www.linkedin.com/in/hswadhwa)

---

BINARY SEARCH TREES
-has a root that is either a node or None
-any node has a most two branches (or children: left subtree and right subtree)
-the children are also binary trees
-different from binary trees (note: no SEARCH in the name)
-left node is smaller in value compared to parent value
-right node is greater in value compared to parent value

INSERT:
-lower value goes to left
-greater value goes to right
-same value doesn't get put in (actually, depends on code)

PREorder (visit node in the BEGINNING)
1) VISIT NODE
2) TRAVERSE LEFT
3) TRAVERSE RIGHT 

POSTorder (visit node in the END)
1) LEFT
2) RIGHT
3) VISIT NODE

INorder (visit node in the MIDDLE)
1) LEFT
2) VISIT NODE
3) RIGHT

Example : 3,15,13,16,21,20,5,18,19

PREorder : 3,15,13,5,16,21,20,18,19
INorder :  3,5,13,15,16,18,19,20,21
POSTorder : 5,13,19,18,20,21,16,15,3

Let's just try to visit all the nodes once, and only once
Dont worry about the order !
Hmm. Let's use a container.

#Algorithm 

my_container.put(head)
while(not container.is_empty()):
    next_node = container.pop()
    print(next_node)
    for each child:
        container.put(child) #from left to right


1. If the container was a stack?
3,15,16,21,20,18,19,13,5

2. If the container was a queue?
3,15,13,16,5,21,20,18,19

Do you notice anything interesting ?
# stack ---> depth first search
# queue ---> breadth first search

---

By Harmanraj Singh Wadhwa (www.linkedin.com/in/hswadhwa)