CODEWITHSUNDEEP
algorithmdata-structurestreebinary-search-tree
GregRos
GregRos

Reputation: 9133

Proving that in-order traversal of binary search tree is sorted (without induction)

Can I prove that traversing binary search tree in-order yields a sorted progression of values, without using induction?

This isn't really a homework question.

Upvotes: 2

Views: 3516

Answers (1)

Rafe
Rafe

Reputation: 5295

Here's my sketch of a proof by contradiction.

Our goal is to show that in-order traversal of a finite ordered binary tree produces an ordered sequence.

To prove this by contradiction, we start by assuming the opposite: that there exists some ordered binary tree such that its in-order traversal yields a non-ordered sequence. Since our trees are finite, there must be a minimal such instance. Let's call this tree T.

Now, T cannot be a singleton (i.e., just a leaf) because the traversal of a singleton yields a sequence of length one, which is trivially ordered.

Therefore T must have some shape, L-x-R where x is a vertex value connecting left and right subtrees L and R respectively.

Since T is minimal and ordered, L and R must be ordered trees whose in-order traversals produce ordered sequences. Moreover, we know that all items in L can be no greater than x and all items in R can be no smaller than x. Now, the traversal of T is [T] = [L] ++ [x] ++ [R]. But this sequence must be ordered, which contradicts our initial assumption concerning T.

Therefore no such T exists, hence in-order traversal of any ordered binary tree must produce an ordered sequence.

Howzat?

Upvotes: 3

Related Questions