In-order traversal : Binary search tree vs. Heap
  • binarysearchtree
  • heap
  • inordertraversal
  •   
  • Posted: 4 years ago
  • Edit
  • answers (1)
  • views (4512)

An in-order traversal of a binary search tree results the elements of an n node tree in sorted order in O(n) time. Can heap do the same?


Posted Answers

While in-order traversal heap will not sort the elements. Heap property states that the left child and right child of a node (n) contains elements lesser (or greater for min heap) than itself. If we perform in-order traversal on heap, it will print the element lesser than n first - left child, then n, and then the right child (but in this case the right child is less than n). So the elements are not printed in sorted order.

You need to Sign In to post your solution.