Pseudocode for non-recursive implementation of tree height and isBST

Question

I am in the process of converting a recursive function to BST not recursive to help prepare for the interview. So far I have been figuring out pre-order, order, order, search, delete, insert and convert BST to a circular linked list. I find it difficult to understand how to use the stack or queues to get the height and find if it is a BST. Any advice would be greatly appreciated. I am not looking for code other than code logic.

Answer 1

Firstly, great work getting ready for such an interview! I hope you enjoy playing with these algorithms.

Let's start with the task to determine if the binary tree is a BST. One way to do this is to take a normal tree walk and check if the items are sorted in sort order. This will be true if and only if the tree is a BST. Since you already have code to move through the elements of the tree in order, you should easily adapt your code to check if the elements coming out of the inorder are sorted by tracking the last element that you saw in moving in order, and then compare each item generated with the previous item. If these two are out of order, the tree is not a BST.

To determine the height of the tree, one option is to select any of the searches you found (preorder, postorder, inorder) and track the height of the stack at each point. The idea here is that since your stack will always keep track of the path back from any node to the root, you can just walk through the tree and record the deepest thing you have ever seen when the stack becomes. This maximum depth is the height of the tree.

Hope this helps! And good luck with the interview!

Answer 2

To find the height of the tree, you can use the Morris traversal [O (n) time]].

To check if it is a valid BST, perform a normal tree move. Move the elements to an array. Check if array is sorted to check BST.