DataStructures-and-Algorithms

Implementation: Trees

Specifications

• Read all of these instructions carefully.
• Name things exactly as described.
• Do all your work in a your data-structures-and-algorithms public repository.
• Create a new branch in your repo named as noted below.
• Follow the language-specific instructions for the challenge type listed below.
• Update the “Table of Contents” - in the README at the root of the repository - with a link to this challenge’s README file.

Challenge Setup & Execution

Branch Name: trees

Challenge Type: New Implementation

Features

Node

• Create a Node class that has properties for the value stored in the node, the left child node, and the right child node.

Binary Tree

• Create a Binary Tree class
  • Define a method for each of the depth first traversals:
    • pre order
    • in order
    • post order which returns an array of the values, ordered appropriately.

Binary Search Tree

• Create a Binary Search Tree class
  • 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.

Structure and Testing

Utilize the Single-responsibility principle: any methods you write should be clean, reusable, abstract component parts to the whole challenge. You will be given feedback and marked down if you attempt to define a large, complex algorithm in one function definition.

Be sure to follow your language/frameworks standard naming conventions (e.g. C# uses PascalCasing for all method and class names).

Any exceptions or errors that come from your code should be contextual, descriptive, capture-able errors. For example, rather than a default error thrown by your language, your code should raise/throw a custom error that describes what went wrong in calling the methods you wrote for this lab.

Write tests to prove the following functionality:

1. Can successfully instantiate an empty tree
2. Can successfully instantiate a tree with a single root node
3. For a Binary Search Tree, can successfully add a left child and right child properly to a node
4. Can successfully return a collection from a preorder traversal
5. Can successfully return a collection from an inorder traversal
6. Can successfully return a collection from a postorder traversal

7. Returns true

   false for the contains method, given an existing or non-existing node value

Ensure your tests are passing before you submit your solution.

Stretch Goal

Create a new branch called k-ary-tree, and, using the resources available to you online, implement a k-ary tree, where each node can have any number of children.

Documentation: Your README.md

# Trees
<!-- Short summary or background information -->

## Challenge
<!-- Description of the challenge -->

## Approach & Efficiency
<!-- What approach did you take? Why? What is the Big O space/time for this approach? -->

## API
<!-- Description of each method publicly available in each of your trees -->

Submission Instructions

1. Create a pull request from your branch to your main branch
2. In your open pull request, leave as a comment a checklist of the specifications and tasks above, with the actual steps that you completed checked off
3. Submitting your completed work:
   1. Copy the link to your open pull request and paste it into the corresponding assignment
   2. Leave a description of how long this assignment took you in the comments box
   3. Add any additional comments you like about your process or any difficulties you may have had with the assignment
4. Merge your branch into main, and delete your branch (don’t worry, the PR link will still work)