English
Menu

Data Structures and Algorithms

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)?

  1. A50, 30, 20, 40, 70, 60, 80
  2. B20, 40, 30, 60, 80, 70, 50
  3. C20, 30, 40, 50, 60, 70, 80
Show answer and explanation

Answer: B. 20, 40, 30, 60, 80, 70, 50

The root is 50; its left child is 30 (with children 20 and 40) and its right child is 70 (with children 60 and 80). Post-order visits the left subtree as 20, 40, 30 and the right subtree as 60, 80, 70, and only then the root 50. 50, 30, 20, 40, 70, 60, 80 is the pre-order result, which visits each node first, and 20, 30, 40, … is the in-order result. Post-order is used when children must be processed first, such as when deleting a tree or producing postfix notation from an expression tree.

  • A. This is the pre-order result, which visits each node before its subtrees.
  • B. Correct. Each node is visited after its left and right subtrees, so the root 50 comes last.
  • C. This is the in-order result, which lists the values in ascending order.
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 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?
  2. 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?
  3. 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?
  4. 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?
  5. In an undirected graph, the neighbors of each vertex are A: B, C / B: A, D, E / C: A, F / D: B / E: B, F / F: C, E. A recursive depth-first search starts from vertex A. The neighbors are examined in the order listed, and as soon as an unvisited vertex is found, the search moves to it. In what order are the vertices visited?