reading-notes

Class 15 Reading: Trees

Resources

• Trees

Trees

To turn in your reading “Reply” to this discussion by teaching something that you learned. Then review what one of your classmates learned, and leave a comment.

Some ideas for how you might want to teach:

• Use an analogy
• Explain a detail in depth
• Use WHY, WHAT, HOW structure
• Tutorial / walk through an example
• Write a quiz
• Create a vocabulary/definition list
• Write a cheat sheet
• Create a diagram / visualization / cartoon of a topic
• Anthropomorphize the concepts, and write a conversation between them
• Build a map of the information
• Construct a fill-in-the-blank worksheet for the topic

Vocabulary Terms

1. Node
   • A node is the individual item/data that makes up the data structure
2. Root
   • The root is the first/top Node in the tree
3. Left Child
   • The node that is positioned to the left of a root or node
4. Right Child
   • The node that is positioned to the right of a root or node
5. Edge
   • The edge in a tree is the link between a parent and child node
6. Leaf
   • A leaf is a node that does not contain any children
7. Height
   • The height of a tree is determined by the number of edges from the root to the bottommost node
8. K
   • K is a number that specifies the maximum number of children any node may have in a k-ary tree. In a binary tree, k = 2
9. Depth First
   • Depth first traversal is where we prioritize going through the depth (height) of the tree first. We can use recursion to implement depth first traversal
10. Breadth First
    • Breadth first traversal iterates through the tree by going through each level of the tree node-by-node
11. Pre-order
    • Pre-order traversal is a type of depth-first traversal that visits a node prior to its children nodes
12. In-order
    • In-order traversal is a type of depth-first traversal that visits a node prior to its children nodes
13. Post-order
    • Post-order traversal is a type of depth-first traversal that visits a node after its children nodes
14. Recursion
    • Recursion is the process of repeating items in a self-similar way
15. Traversal
    • Traversal is the process of iterating through a data structure (e.g., an array) and performing a specific action on each element in the data structure
16. Binary Tree
    • A binary tree is a tree data structure in which each node has at most two children, which are referred to as the left child and the right child
17. Binary Search Tree
    • A binary search tree, sometimes called ordered or sorted binary trees, are a particular type of container: data structures that store “items” (such as numbers, names etc.) in memory
18. K-ary Tree
    • A k-ary tree is a rooted tree in which each node has no more than k children
19. Balanced Tree
    • A tree where the difference between the depths of any two leaf nodes (the leaf nodes being the nodes furthest from the root) is no greater than one
20. Perfect Binary Tree
    • A perfect binary tree is a binary tree in which all interior nodes have two children and all leaves have the same depth or same level
21. Unbalanced Tree
    • A tree where the difference between the depths of any two leaf nodes (the leaf nodes being the nodes furthest from the root) is greater than one
22. Big O
    • Big O notation is used in Computer Science to describe the performance or complexity of an algorithm

Reflection

1. What did you learn after reviewing a classmates reply to this thread?

   • Well, not much that I didn’t learn from the reading because we literally all read the same document. But I did learn that I’m not the smortest fella. In fact, I think the argumnent could be made that with every passing day, I push the known limits of intellectual poverty.