Inorder of a BST

Exercise 3.10

Prove that the in-order traversal of a binary search tree visits the elements in increasing order.

Hint

By induction on the height of the tree.

Recall that (in computer science), a tree traversal is a form of graph traversal and refers to the process of visiting (e.g. retrieving, updating, or deleting) each node in a tree data structure, exactly once. Such traversals are classified by the order in which the nodes are visited.

The in-order transversal recursively traverse the current node’s left subtree, then visit the current node, and finally recursively traverse the current node’s right subtree.