English
Menu

Data Structures and Algorithms

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?

  1. A10
  2. B500
  3. C1,000
Show answer and explanation

Answer: C. 1,000

When values are inserted in ascending order, each new value becomes the right child of the previous maximum, so the tree becomes a single chain extending only to the right (height 999). 1000 is at the very bottom, so it is compared with all 1,000 nodes, 1, 2, …, 1000, which is O(n), the same as walking a linked list from the front. A balanced tree would have only about log₂ 1000 ≈ 10 levels, so using a self-balancing binary search tree such as an AVL tree or a red-black tree, which reshapes itself on every insertion and deletion, keeps the worst case at O(log n).

  • A. A balanced tree would need about 10, but this tree has become a single chain.
  • B. This is close to searching for a value in the middle, but 1000 is at the end.
  • C. Correct. The tree is a single chain, so finding 1000 means comparing every node.
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. 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?
  2. 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?
  3. 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?
  4. 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?
  5. In an undirected graph, the edge weights (distances) are S−A: 4, S−B: 1, A−B: 2, A−C: 1, B−C: 5, C−T: 3 and A−T: 6. Which shows the shortest path from S to T found by Dijkstra's algorithm and its length?