【第三轮】7.7-7.13 CareerCup 4.5

4.5 Implement a function to check if a binary tree is a binary search tree.

回复解法可以按照以下格式来

【解题思路】
【时间复杂度】
【空间复杂度】
【gist link】
---------------Optional，如果觉得test case比较好，欢迎写出来分享----------------------
【test case】

Notice：
1、记得在程序注释中表明自己算法的时间、空间复杂度
2、代码难懂之处加注释
3、每道题目有对应的帖子，除了贴解法，欢迎讨论，集思广益
4、任何未尽之处，欢迎回报名帖提问，我会进一步作出修改。

【解题思路】
BFS - perform a inorder traversing, keep tracking two consecutive visited nodes, if the current one's value is smaller than the previous one, return false since BST is monotonic increasing inorder.

【时间复杂度】
O(N)

【空间复杂度】
O(N)

【gist link】
https://gist.github.com/chrislukkk/24270f55880fa1060d53
binray tree & tree builder:
https://gist.github.com/chrislukkk/2a1f825b8e924ea773e8

【解题思路】
1. left.data < curr.data < right.data, recursively check left and right child (WRONG!!! NOT SUFFICIENT CONDITION!!!)
2. in-order traversal, keep track with the previous value and compare to the current one
3. check whether ALL left nodes are less than or equal to the current node, which must be less than ALL the right nodes
【时间复杂度】
O(N)
【空间复杂度】
O(N)
【gist link】
https://gist.github.com/bcb725181e5a8f6035f3
【test case】
build binary tree using function developed in 4.3
array = [5 10 25 20 25 30 35]
Expected output: 0 (false)
Approach 1: 1
Approach 2: 0
Approach 3: 0

【解题思路】
recursion: check from root to leaves, passing the left & right bound to every sub-call

【时间复杂度】
O(n)

【空间复杂度】
O(logn)

【gist link】
https://gist.github.com/happyWinner/7023673688565a1f402

【解题思路】
遍历每个点，保证右支的点都大，左支的点都小
【时间复杂度】
O(N)
【空间复杂度】
O(N)
【gist】
https://github.com/donnice/donnice/blob/master/Q4_5

【解题思路】BST each node, compare left to current, current to right. Ref to 2nd codes
【时间复杂度】
O(N)
【空间复杂度】
O(N)
【gist】https://gist.github.com/bitcpf/2d94f8556e160d311d96

【解题思路】
recursion with min and max limitation
【时间复杂度】
O(N)
【空间复杂度】
O(log N)
【gist】
https://gist.github.com/JoyceeLee/afb2727dc92838e881be

【解题思路】Inorder transverse the tree, check predecessor is smaller than current node
【时间复杂度】O(N)
【空间复杂度】O(1)
【gist】https://gist.github.com/nealhu/9b8c4f9e306e61c3f0bd

【解题思路】
recursively traverse the binary tree, compare the node with min and max value
【时间复杂度】
O(N)
【空间复杂度】
O(N)
【gist】
https://gist.github.com/iwilbert/eb5b9c51613be3224aba