I'm trying to check if the binary tree is binary search tree. My idea is to use Morris traversal. Intuitively a binary tree is balanced iff Morris traversal produces a sorted threaded linked list.
The problem is I could not prove this proposition strictly. Is it even correct so it's safe to use it for binary search tree validation?
A binary tree is a binary search tree iff its inorder traversal yields an ordered list.
Inorder (or symmetric) traversal is recursively defined as left-node-right. This recurrence is of course directly connected to the defining property of search trees: the items of the left subtree are smaller than the root, which in turn is smaller than the items of the right subtree. This makes the statement above rather straightforward.
So, in order to test the tree one needs to perform an inorder traversal. It is not important whether that traversal is done with recursion, with a stack or with temporal threads using Morris traversal.
(I am a little puzzled by your use of the word balanced. Usually that is related to the number of nodes or heights in subtrees.)
