English
Menu

Data Structures and Algorithms

When a binary search tree is traversed in in-order (visiting the left subtree, then the node, then the right subtree), how are the values of the visited nodes ordered? Assume all values are distinct.

  1. AIn ascending order (smallest first)
  2. BIn the order they were inserted
  3. CIn order of closeness to the root (shallowest first)
Show answer and explanation

Answer: A. In ascending order (smallest first)

In a binary search tree, for every node, all values in the left subtree are smaller than the node and all values in the right subtree are larger. Visiting the left subtree, the node and then the right subtree therefore visits the values from smallest to largest, so the result is in ascending order. Visiting nodes in order of closeness to the root is a breadth-first (level-order) traversal, which goes level by level from left to right. The insertion order affects the shape of the tree but does not match the order of any of these traversals.

  • A. Correct. Since the left side is smaller and the right side larger, in-order traversal gives ascending order.
  • B. The insertion order affects the tree's shape, but in-order traversal gives ascending order regardless of it.
  • C. This is the result of a breadth-first (level-order) traversal, which visits the tree level by level.
Practice this topic Back to topic

Related calculators

Binary search tree and heap visualizerDraw the binary search tree or heap built by inserting values in order, and show the preorder, inorder and postorder traversals, the search path and the heap's array layoutSorting algorithm visualizerWatch 7 sorting algorithms (bubble, selection, insertion, shell, merge, quick and heap) step by step as bar charts, and compare their comparison and write counts

Books on Data Structures and Algorithms Ad

As an Amazon Associate I earn from qualifying purchases.

More Data Structures and Algorithms questions

  1. The values 50, 30, 70, 20, 40, 60, 80 are inserted in this order into an empty binary search tree. In what order are the nodes visited when the tree is traversed in post-order (left subtree, right subtree, then the node)?
  2. The values 1, 2, 3, …, 1000 are inserted in this order into an empty binary search tree (no rebalancing is done). When searching this tree for 1000, how many nodes are compared, starting from the root, before it is found?
  3. What is the main reason that B-trees (including B+ trees), rather than binary search trees, are widely used for indexes in databases and file systems?
  4. Which is an appropriate way to store in memory a sparse graph, one with few edges compared with its number of vertices, such as a road network with about 1 million vertices and 3 million edges?
  5. In a graph whose edges have no weights, you want to find the smallest number of edges from a starting vertex to every other vertex. Which pair of search method and data structure is suitable?