Binary tree traversals
The four traversals of a binary tree (preorder, inorder, postorder, level order), their visit order, the link with prefix, infix and postfix notation of an expression, and rebuilding the tree from two traversals.
- 29 cards
- 5 topics
- Free
The outline, topic by topic
Each topic is weighted the way the exam weighs it.
- Concepts
- Questions
- Sort and link
- The numbers
- Understand
A few cards from the deck
Binary tree: what is it?
Show the answer
A rooted tree where each node has at most two children, told apart as left child and right child, each the root of a subtree.
Left and right matter: a node whose only child is on the left and one whose only child is on the right give two different binary trees.
Binary tree: P has the children Q (left) and R (right); Q has only a right child, S; R has the children T (left) and U (right). What is the postorder traversal?
- S Q T U R P
- P Q S R T U
- Q S P T R U
- P Q R S T U
Show the answer
S Q T U R P
Postorder: left subtree (S Q), right subtree (T U R), then P. P Q S R T U is the preorder, Q S P T R U the inorder and P Q R S T U the level order of the same tree.
The … traversal of a binary search tree gives its values in … order.
Show the answer
The inorder traversal of a binary search tree gives its values in increasing order.
The whole left subtree is smaller than the root, the whole right subtree larger: left, root, right is already sorted.
Preorder traversal: what is it?
Show the answer
A depth-first traversal that visits the root, then the left subtree, then the right subtree.
The root comes first at every level: this is the order for copying a tree or writing an expression in prefix notation.