Trees
A binary search tree is a rooted binary tree with labelled nodes. The nodes are labelled with representations of the members of the set. Each node except the root has an incoming branch from its parent. For uniformity, each node is considered to have two outgoing branches, called left and right.
Challenge
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
Create a Binary Search Tree class
This class is sub-class from binary Tree class
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.
Approach & Efficiency
Big O insert log(n) because there is a loop but each itarate i ignore halve of the tree contain log(n) because there is a loop but each itarate i ignore halve of the tree
API
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.
Challenge Summary 16
Find the Maximum Value in a Binary Tree
Whiteboard Process
Approach & Efficiency
Time O(n) because we iterate inside while loop space O(1) because we didn’t assign more than one in the same time
Solution
you can run the library and see the output from there
Challenge Summary
Write a function called breadth first Arguments: tree Return: list of all values in the tree, in the order they were encountered
Whiteboard Process
Approach & Efficiency
explaind in white board
Solution
you can run the library and see the output from there
Challenge Summary
Conduct “FizzBuzz” on a k-ary tree while traversing through it to create a new tree.
Set the values of each of the new nodes depending on the corresponding node value in the source tree.
Whiteboard Process
Approach & Efficiency
explaind in white board
Solution
you can run the library and see the output from there