Trees (Module 8.1) Flashcards
What is a collection of nodes?
trees
Trees are inherently ___________!
recursive
There are _____ nodes in a tree.
N
There are _________ edges in a tree.
N-1
What are nodes with the same parent called?
siblings
What are nodes with no children called?
leaves
What is a sequence of nodes in which each successive node is connected by an edge to the previous node?
path
What determines the depth of a node?
the length from the root
What is the height of a node?
the longest path from the node to a leaf
How many parents can a tree node have?
1
Can tree nodes have cycles?
No!
Tree nodes can’t have children that are __________ or __________ on the tree
on the same level, above
Which traversal method visits nodes by exploring as far down a branch as possible before backtracking?
Depth-First Traversal
What are the 3 variations for Depth-First Traversal?
1) Preorder Traversal
2) Inorder Traversal
3) Postorder Traversal
What is the order for Preorder Traversal?
Root –> Left –> Right
What is the order for Inorder Travel?
Left –> Root –> Right
What is the order for Postorder Traversal?
Left –> Right –> Root
Which traversal method visits nodes level by level, starting at the root and moving horizontally across each level?
Breadth-First Traversal
How is Breadth-First traversal usually implemented to track nodes at the current level?
using a queue
What is the variation for Breadth-First traversal that’s useful for finding the shortest path or levels in a tree?
Level Order
Are Depth-First Traversal algorithms recursive?
Yes!
