Node
Create a Node class that has properties for the value stored in the node, the left child node, and the right child node.
Create a Binary Tree class Define a method for each of the depth first traversals:
- pre order
- in order
- post order Each depth first traversal method should return an array of values, ordered appropriately.
Binary Search Tree
This class should be a sub-class (or your languages equivalent) of the Binary Tree Class, with the following additional methods:
Add Arguments: value Return: nothing
- Adds a new node with that value in the correct location in the binary search tree.
Contains Argument: value Returns: boolean indicating whether or not the value is in the tree at least once.
I attempted to do these methods with a different iterative method instead of just plain recursion, but I don't know if that's better or not.
Time: O(n)
- for inserting and searching. Worst case is that you have to traverse the entire tree.
Space: O(w)
- for insertion/search, where width is the largest width of the tree.
Terminal command for general main module: python3 -m binary_search_tree.binary_search_tree
Terminal command for testing in pytest: python3 -m pytest binary_search_tree/
