Implementation: Trees
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
Binary Trees, Binary Search Trees, and K-ary Trees
Fill in the Blank
-
A Tree _____ is a component which may contain its own values, and references to other nodes.
a. stack b. root c. branch d. node
-
A reference to a child node in a binary tree is either __ or __.
a. top, bottom b. leaf, branch c. left, right d. root, top
-
The __ in a tree is the link between a parent and child node.
a. stem b. fruit c. edge d. link
-
A childless Node is referred to as ___.
a. root b. nut c. sample d. leaf
Answers are at the bottom of the notes.
Notes
Transversals
An important aspect of trees is how to traverse them. Traversing a tree allows us to search for a node, print out the contents of a tree, and much more! There are two categories of traversals when it comes to trees:
Depth First Breadth First
*Depth First
Depth first traversal is where we prioritize going through the depth (height) of the tree first. There are multiple ways to carry out depth first traversal, and each method changes the order in which we search/print the root. Here are three methods for depth first traversal:
Pre-order: root » left » right In-order: left » root » right Post-order: left » right »
rootALGORITHM preOrder(root)
OUTPUT <– root.value
if root.left is not NULL preOrder(root.left)
if root.right is not NULL preOrder(root.right)
Traversal Pseudocode
Pre-order
ALGORITHM preOrder(root) // INPUT <– root node // OUTPUT <– pre-order output of tree node’s values
OUTPUT <-- root.value
if root.left is not Null
preOrder(root.left)
if root.right is not NULL
preOrder(root.right)
In-order
ALGORITHM inOrder(root) // INPUT <– root node // OUTPUT <– in-order output of tree node’s values
if root.left is not NULL
inOrder(root.left)
OUTPUT <-- root.value
if root.right is not NULL
inOrder(root.right)
Post-order
ALGORITHM postOrder(root) // INPUT <– root node // OUTPUT <– post-order output of tree node’s values
if root.left is not NULL
postOrder(root.left)
if root.right is not NULL
postOrder(root.right)
OUTPUT <-- root.value
Breadth
Uses a queue instead of stack
Order would be A,B,C,D,E
using enqueue and dequeue
Pseudocode
ALGORITHM breadthFirst(root) // INPUT <– root node // OUTPUT <– front node of queue to console
Queue breadth <– new Queue() breadth.enqueue(root)
while ! breadth.is_empty() node front = breadth.dequeue() OUTPUT <– front.value
if front.left is not NULL
breadth.enqueue(front.left)
if front.right is not NULL
breadth.enqueue(front.right)
Adding a node
Because there are no structural rules for where nodes are “supposed to go” in a binary tree, it really doesn’t matter where a new node gets placed.
One strategy for adding a new node to a binary tree is to fill all “child” spots from the top down. To do so, we would leverage the use of breadth first traversal. During the traversal, we find the first node that does not have all its children filled, and insert the new node as a child. We fill the child slots from left to right.
In the event you would like to have a node placed in a specific location, you need to reference both the new node to create, and the parent node which the child is attached to.
Big O The Big O time complexity for inserting a new node is O(n). Searching for a specific node will also be O(n). Because of the lack of organizational structure in a Binary Tree, the worst case for most operations will involve traversing the entire tree. If we assume that a tree has n nodes, then in the worst case we will have to look at n items, hence the O(n) complexity.
The Big O space complexity for a node insertion using breadth first insertion will be O(w), where w is the largest width of the tree. For example, in the above tree, w is 4.
A “perfect” binary tree is one where every non-leaf node has exactly two children. The maximum width for a perfect binary tree, is 2^(h-1), where h is the height of the tree. Height can be calculated as log n, where n is the number of nodes.
Binary Search Trees
A Binary Search Tree (BST) is a type of tree that does have some structure attached to it. In a BST, nodes are organized in a manner where all values that are smaller than the root are placed to the left, and all values that are larger than the root are placed to the right.
Searching a BST Searching a BST can be done quickly, because all you do is compare the node you are searching for against the root of the tree or sub-tree. If the value is smaller, you only traverse the left side. If the value is larger, you only traverse the right side.
example Let’s say we are searching 15. We start by comparing the value 15 to the value of the root, 23.
15 < 23, so we traverse the left side of the tree. We then treat 8 as our new “root” to compare against.
15 > 8, so we traverse the right side. 16 is our new root.
15 < 16, so we traverse the left side. And aha! 15 is our new root and also a match with what we were searching for.
The best way to approach a BST search is with a while loop. We cycle through the while loop until we hit a leaf, or until we reach a match with what we’re searching for.
Big O The Big O time complexity of a Binary Search Tree’s insertion and search operations is O(h), or O(height). In the worst case, we will have to search all the way down to a leaf, which will require searching through as many nodes as the tree is tall. In a balanced (or “perfect”) tree, the height of the tree is log(n). In an unbalanced tree, the worst case height of the tree is n.
The Big O space complexity of a BST search would be O(1). During a search, we are not allocating any additional space.
Things I want to know more about
great visualization of binary trees. You add and create your own nodes and perform most functions that you would need to do with a tree (insert, search, remove…etc) https://visualgo.net/en/bst?slide=1
Answer key: d,c,c,d