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?


1 Answer 1


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.)


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.