Trees Flashcards
What is the order of nodes visited in an inorder traversal of a binary tree?
Left subtree, root, right subtree.
True or False: Inorder traversal of a binary tree results in nodes being visited in ascending order for a binary search tree.
True.
What data structure is commonly used to implement iterative inorder traversal?
Stack.
Fill in the blank: Inorder traversal is defined as visiting the _______ first, then the root, and finally the _______.
left subtree; right subtree.
How do you perform a recursive inorder traversal?
Visit the left subtree, then the root, and finally the right subtree recursively.
What is the time complexity of inorder traversal?
O(n), where n is the number of nodes in the tree.
Which traversal method would you use to retrieve values in non-decreasing order from a binary search tree?
Inorder traversal.
True or False: Inorder traversal can be applied to non-binary trees.
False.
What is the space complexity for recursive inorder traversal?
O(h), where h is the height of the tree.
Which of the following is NOT a type of tree traversal? A) Inorder B) Preorder C) Postorder D) Sideorder
D) Sideorder.
What is the result of inorder traversal on the following binary tree: 1 (root), 2 (left child), 3 (right child)?
2, 1, 3.
Fill in the blank: In a binary tree, inorder traversal visits the _______ child before the root.
left.
What is the primary purpose of inorder traversal?
To retrieve nodes in a sorted order for binary search trees.
True or False: Inorder traversal modifies the structure of the binary tree.
False.
What is the main difference between inorder and preorder traversal?
Inorder visits left child, root, then right; preorder visits root, left child, then right.
What is the iterative algorithm for inorder traversal?
Use a stack to keep track of nodes; push left children until reaching null, then process the node and move to the right.
In a binary tree with only one node, what is the result of an inorder traversal?
The single node itself.
Fill in the blank: Inorder traversal is one of the _______ methods used to traverse a binary tree.
depth-first.
Which traversal would you use to create a sorted list from a binary search tree?
Inorder traversal.
True or False: The inorder traversal of a tree is unique.
False; different trees can have the same inorder traversal.
What does the term ‘height of the tree’ refer to?
The length of the longest path from the root to a leaf.
How many times is the root node visited during an inorder traversal?
Once.
What is the key advantage of using an iterative approach for inorder traversal?
It avoids the risk of stack overflow with very deep trees.
Fill in the blank: The inorder traversal of a complete binary tree produces a _______ output.
sorted.
