Binary Search Trees Lesson Notes

binary-search-trees.md

Binary Search Trees

Objectives

• Define what a binary search tree is
• Explain why binary search trees are useful
• Write pseudo code to traverse a binary search tree
• Explain the difference between depth first search methods (pre-order, in-order, post-order)
• Describe the Big O of binary search tree methods
• Implement binary search tree methods

Guiding Questions

• What is a binary search tree? What are it's restrictions? When might they useful?

  Binary Search Tree is a node-based binary tree data structure which has the following properties: The left subtree of a node contains only nodes with keys lesser than the node’s key. The right subtree of a node contains only nodes with keys greater than the node’s key. The left and right subtree each must also be a binary search tree. Each node must be unique.

• Diagram the following set of numbers as a binary search tree:

  • 1, 3, 4
  • 3, 1, 4
  • 5, 3, 8, 4, 0, 6, 7

  Your answer...

• How do you traverse a binary search tree? What is depth first search? How do Pre-order, In-order and Post-order differ?

  Your answer...

• What is the Big-O of Binary Search Trees methods (best and worst case):

  • Insert
  • Remove
  • Lookup
  • Traverse

  Your answer...

• Practice working with trees

  https://github.com/gSchool/trees-assessment

Resources

• https://stackoverflow.com/questions/2130416/what-are-the-applications-of-binary-trees
• https://en.wikipedia.org/wiki/Tree_traversal
• https://www.cs.usfca.edu/~galles/visualization/BST.html
• https://visualgo.net/bn/bst
• https://www.geeksforgeeks.org/binary-tree-set-1-introduction/

Implementation

Start by forking and cloning the checkpoint repo: https://github.com/gSchool/binary-search-trees Implement the following methods on the BinarySearchTree class:

• insert()
• DFSPreOrder()
• DFSPostOrder()
• findDFS()
• size()
• breadthFirstSearch()
• findBFS()