Tree-traversal
No description yet. This curated deck is ready for daily study.
Card preview (10)
What are the 3 most common algorithms for traversing trees?
Pre-order, post-order and in-order
Define pre-order
Specifies the point in traversal where the node contents are processed
What happens to a node when it’s visited?
A nodes contents are outputted
How many times can a node be visited?
Multiple times but it’s contents can only be processed once
What makes pre-order traversal special?
Each node is visited before the algorithm traverses either of the nodes subtrees
State the simplified recursive algorithm for a left-right pre-order traversal
Visit the node Pre-order traverse of nodes left sub tree pre-order traverse of the nodes right subtree
What happens in an in-order traversal?
Each node is visited between each of it’s subtrees
State the simplified algorithm for a left-right in-order traversal
Do an in-order traversal of the whole left subtree visit the node in-order traverse the right subtree
What happens in a post-order traversal?
Each node is visited after both of it’s subtrees
State the simplified recursive algorithm for a left-right post-order traversal
Do a post-order traversal of the left subtree Do a post-order traversal of the right subtree Visit the node