Data Structures: Binary Search Tree

Learn how to detect if a tree is a valid binary search tree. This video is a part of HackerRank's Cracking The Coding Interview Tutorial with Gayle Laakmann McDowell.

[stackingflow]

The way of her teaching is super good, I wish she had some youtube channel or paid course with more videos. loving it

[federicocapaldo]

Suggestion:
The video actually presents how to check if a binary tree is a search tree. It does not discuss the Binary Search Tree implementation itself. it would be great to have a video on that and to change the title of this video.

[nishantgarg]

I haven't watched the full video but just heard the question and writing my thought on this. The best solution that I came up with this is to go for In-Order Traversal of the BST. If u see the In order traversal of BST is always increasing order. So u just want to have 2 element array in which the inorder traversal is getting stored and replaced.

For Example, the In order Traversal is as 1, 2, 3, 4, 5, 6, 7, 8, 9, 10. Now store it in arr[2] like this:-
1. arr[0]=1, arr[1]=2. Is arr[0]<arr[1]. Yes? then move to next.
2. arr[0]=1, arr[1]=3. Is arr[0]<arr[1].Yes? then repeat.
3. arr[0]<arr[1]. False? Then break the loop and just print that given tree is not BST.

I gave this answer during my interview with the amazon and he was impressed that i came up with this solution in such short amount of time.

[radsimu]

just do an inorder pass and check that what you get is sorted every time you add a new value to the resulting array - done. But still, if you don't figure that out on the spot, computing min max on all branches recursively should also take O(n) just that you need to write a lot more code

[adirmugrabi]

at 5:40 you said that you must have a return true;
that is false.
since what if the recursive call is :
return !foo(variables);

i can't think of an example where that would be useful RN, but it is possible

[cemalcakir]

Gayle Laakmann McDowell is the legend!

[MustafaDagher]

the time complexity of this is o(n), you will have to visit every single node in the tree.

unlike the binary search, where you exclude complete halfs of the elements everytime you recurse

[JamesCalcagni]

is it okay to name both boolean functions the same "checkBST" as is the way she has it? don't they need to be different?

[jackliang]

After watching the Data Structures:Trees video, this feels like deja vu

[claybar]

Pretty sure the space complexity is linear as well, not logarithmic.