Today's excercise was Validate Binary Search Tree
While I though I had a working solution, it seemed to be failing at certain cases. When I fixed it for those, it was failing for the earlier ones. After peeking at the solution, I realised I had misunderstood what a BST was.
All the values within a tree and it's children, are either greater or lower than it's parent (depending if it a left or right node).
While I was checking for the current node's range, I had not been checking for the range of their children. I just had to account for a range that was passed down to each validation and found the solution !
That got me wondering, is a range required ?
When I looked at how the values are placed when an inorder traversal is made, I noticed how each value has to be smaller than the one before. This created essentialy an ascendingly ordered array. With this, I was able to craft another solution where the range isn't needed, just a variable outside the validate context to keep track of the previous value.
While I though I had a working solution, it seemed to be failing at certain cases. When I fixed it for those, it was failing for the earlier ones. After peeking at the solution, I realised I had misunderstood what a BST was.
All the values within a tree and it's children, are either greater or lower than it's parent (depending if it a left or right node).
While I was checking for the current node's range, I had not been checking for the range of their children. I just had to account for a range that was passed down to each validation and found the solution !
That got me wondering, is a range required ?
When I looked at how the values are placed when an inorder traversal is made, I noticed how each value has to be smaller than the one before. This created essentialy an ascendingly ordered array. With this, I was able to craft another solution where the range isn't needed, just a variable outside the validate context to keep track of the previous value.
