A binary tree is classified as a binary search tree if all the non-null nodes exhibit two properties:
A pre-order traversal is a recursive tree traversal method where the current node is visited first, then the left subtree, then the right subtree. Given a pre-order traversal history of a binary tree, check whether the path represents a valid binary search tree.
Root Node
Next value lower, insert Left
Next value is higher, append to Right of Root
Next value lower, append to Left
Next value higher, append to Right of Subtree. Does not contradict pre-order traversal, hence valid.
This coding exercise was first introduced by my friend, who had this question as part of his interview for a job. This was done before I was familiar with handling such data structures, and I first struggled when encountering this question. While I knew how to develop the data structure, I was stuck for quite a while regarding the traversal of the given inputs.
Initially, I was focused on how to handle the traversal back up from each child node when the next value was larger than the previous. I was not able to come up with a clean and consistent solution that fits for all cases with this method of traversal. The solution came to me after I remembered what I read about regarding trees during my self studies, where they traverse down from the root, which instantly gave way to my solution, resetting my traversal from root each time a value seems like it cannot be inserted.
This exercise was certainly meaningful for me, seeing how this was an actual interview question and how I have to look in other perspectives to come with a clean and consistent solution.