Recently Viewed: Home > Binary Search Tree
 Binary Search Tree
Binary Search Trees And Inorder Traversals

 Designed by Judy Lynn and Cathy Bishop-Clerk.

 This KLA is transcribed from the SIGCSE 2004 Special Session on KLAs.

Overview To KLA

 Learning Goals: At the end of this exercise, students will understand...

 • build a BST
 • traverse in order and verify alphabetic sort

 Course And Level: data structures

 Class Size: up to 27(so far), or small sub tree groups

 Preparation Time: low

 Execution Time: 15 min

Planning For KLA

 Materials:
 • Post-its 1/students - markers
 • large visible surface
 • room to move and lineup

 As always, read this description carefully and practice the KLA before using it in class!

Execution Of KLA

 Description:
 • Each person writes first name on post-it
 • Instructor selects 1 student to be root.
 • That student places post-it high and central and then selects next student.
 • Second and subsequent students say "I'm less/greater than " and go left or right until their position is found.
 • Once tree is built, do an inorder traversal.

 bst.jpg

 — Joe: I can't go I'm waiting for Bob.

 — Bob: I can't go I'm waiting for Ann.

 — Ann: Goes and starts wall against side of classroom and says "I'm done"

 — Bob: Says "I'm done" and stands next to Ann.

 — Joe: "I'm done, Zed your turn."

 — repeat for rest of tree
 • At end, students are all in line and state their names out loud to verify alphabetic order

 Variants And Extra Topics: To be added.

Constraints On KLA

 • Limited Vision: Not if a few were constrained.
 • Limited Hearing: Not if a few were constrained.
 • Limited Mobility: Not if a few were constrained.
 • Trouble Speaking: Not if a few were constrained.
 • Touch Aversion: Not if many were constrained.
 • Other:

Pitfalls Of KLA

Feedback And Use Notes

 Feedback:
 • Good way to explain a difficult process.
 • Good idea.
 • Good idea x 3.