Trees Flashcards
What are the two ways you could view a tree as?
Generalisation of a linked list
Specialisation of a graph
Define a tree
Abstract data type that simulates a hierarchical tree structure, with a root value and subtrees with children
What makes a binary tree special?
Each node has at most two child nodes
What three things are stored in a class for a BinaryTreeNode?
element
left node
right node
Define traversal
Systematic way of accessing or visiting all the nodes
Complexity for insert in a tree
Linear
Complexity for contains in a tree
Linear
Complexity for remove in a tree
Linear
Complexity for size in a tree
Linear
What are the four strategies for traversal?
Breadth first Depth first (in order, post order, pre order)
Describe in order traversal
Visit the first child, visit the node, visit the next
node/child
l n r
Describe post order traversal
Visit the children, visit the node
l r n
Describe pre order traversal
Visit the node, visit the children
n l r
Write a recursive function that does pre order traversal of a tree
public void traverse(BinaryTreeNode node){
visit(node.element)
if(node.left !=null) traverse(node.left)
if(node.right !=null) traverse(node.right)
}
Write a recursive function that does post order traversal of a tree
public void traverse(BinaryTreeNode node){
if(node.left !=null) traverse(node.left)
if(node.right !=null) traverse(node.right)
visit(node.element)
}
Write a recursive function that does in order traversal of a tree
public void traverse(BinaryTreeNode node){
if(node.left !=null) traverse(node.left)
visit(node.element)
if(node.right !=null) traverse(node.right)
}
What is an expression tree?
A tree where in each node can hold an operator or an operand
Different traversals generate different notations and results
Give the name for this notation and what kind of traversal is used to generate it
+ 2 3
Polish notation
Pre-order traversal
Give the name for this notation and what kind of traversal is used to generate it
2 + 3
Infix notation
In order traversal
Give the name for this notation and what kind of traversal is used to generate it
2 3 +
Reverse Polish notation
Post order traversal
What is another name for breadth first traversal?
Level order traversal
What are the two types of search that can be performed on trees?
Depth first search (DFS)
Breadth first search (BFS)
Describe a depth first search
Start at the root
Go as far down as possible each branch before backtracking if the goal has not been found
Describe a breadth first search
Start at the root
Examine all the child nodes
For each child node, examine it’s child nodes
and so on…
Desirable features for searching/sorting data structures in terms of constraints
Unbounded size
Dynamic
Desirable features for searching/sorting data structures in terms of operations
Add/remove
Search/sort
Desirable features for searching/sorting data structures in terms of complexities
Everything O(1) or as close as possible Keep operations scale-able
