mark_philosophe A bit of simple advice for other code travelers: checkBST does not like duplicate values;
Goenka thanks a lot, 3, 6, 7 were failing because of this issue.
lucydryer [deleted]lucydryer [deleted]
antonaut Had exactly the same issue.
More recursion to the people!
My solution:
boolean left(Node root, int pdata) { if (root == null) return true; if (root.data >= pdata) return false; return left(root.left, root.data) && left(root.left, pdata) && left(root.right, pdata) && right(root.right, root.data); } boolean right(Node root, int pdata) { if (root == null) return true; if (root.data <= pdata) return false; return right(root.right, root.data) && right(root.right, pdata) && right(root.left, pdata) && left(root.left, root.data); } boolean checkBST(Node root) { return left(root.left, root.data) && right(root.right, root.data); }
Goenka boolean check(Node root, int min, int max) { if (root != null) { if (root.data >= max || root.data <= min) { return false; } else { return check(root.left, min, root.data) & check(root.right, root.data, max); } } else { return true; } } boolean checkBST(Node root) { return check(root, 0, Integer.MAX_VALUE); }aanandsw what if root has 0 as data :)
aanandsw if (root.data >= max || root.data <= min) { return false;
here it will fail. if there is single node root and root has data 0
anujad I agree. It looks there is no test case covering this scenario.
promptcomster just modified a little thanx it saved my time
boolean checkBST(Node root) { return checkBST1(root,Integer.MIN_VALUE,Integer.MAX_VALUE); } boolean checkBST1(Node root, int min,int max) { if(root==null) return true; if(root.data <=min || root.data >=max) return false; return(checkBST1(root.left,min,root.data) && checkBST1(root.right,root.data,max)); }
aanandsw i have written almost same code as
bool check(Node * node, const size_t& min, const size_t& max) { if(node) { if(!((node->data > min) && (node->data < max))) { return false; } else { return (check(node->left, min, node->data) && check(node->right, node->data, max)); } } return true; } bool checkBST(Node* root) { if(root) { return (check(root->left, 0, root->data) && check(root->right, root->data, -1)); } else { return true; } }
zjuPeco because the data is between [0, 10^4],and is an integer, so
bool checkBST(Node* root) { return check(root, -1, 10001); }
Dharmateja6 could u pls help me how can u pass int min && int max as arguments
victortang_com As you can see from the example above, you define another function which takes in more parameters. It is recommended to use inner function if possible because it hides complexity from the caller.
Krishdgp Can you please explain me why are we calling the function recursively using pdata?
Gameatro [deleted]
Goenka [deleted]keertipurswani27 Why do we need to check 4 cases?checking 2 should be enough right?Why are we checking with pdata?
antonaut I posted this as a kind of joke. It's not a good solution to the problem. It is however a great solution to discuss why it is bad. Indeed, checking two cases should be enough. The pdata is short for 'parent data'. Should have renamed that to clarify the thought process.
VasuSmile Thanks much.. Solved my errors
Chuyinzki breh
bv_bharatk_gmail Thanks a lot mark, saved me lot of time. This should have been mentioned in the problem.
olleh423 THIS IS MY SOLUTION
int recent ;
boolean checkBST(Node root) { if(root == null) return true ;
boolean flag = checkBST(root.left) ; if(flag) { if(recent >= root.data) return false ; else recent = root.data ; } if(flag) flag = checkBST(root.right) ; return flag ;}
mharsha91 Could you please let me know what's the initial value of recent ?
Romilrc Yeah thanx alot some test case were failing because of it
zhouhaoisme get score 20.77......this code!
boolean checkBST(Node root) { return false; }
zakaria_jaiathe Haha Nice one :D
baoxx142 great advice!
amaragrawal Yes.
A single line like below will pass these cases, thanks for saving my time.
if(node.data <= min || node.data >= max) return false;
priyanshu_singh3 thanks ! that helped!!
maverick009 Thanks man..i had this issue with 3,6,7
xdavidliu the actual definition of BST allows duplicate values, as long as their inorder walk is non-decreasing, so that requirement in this problem is actually wrong.
vivek_23 Well , I just did an inorder traversal, stored them in a list and checked if they are in ascending order. If yes, then its a BST , else it isn't.
This would work for all values (signed or unsigned) a node can possess.
When compared with recursion (which has stack depth), space complexity remains the same in worst case.
Time complexity also remains O(n) , only difference being that mine is a 2-pass solution.
Tofurkey I did this as well!
alvinpon I used the same method like you, but I passed all solutons, but I have no idea why my recusive method can't pass all.
vivek_23 Can you share your recursive code ?
pinkRanger Hey ,Even I tried the recursive method but all the test cases didnt pass, Please check the code
bool checkBST(Node* root) { struct Node *tmp=(struct Node*)malloc(sizeof(struct Node)); tmp=root; if(root==NULL) return true; else if(tmp->left!=NULL && tmp->right!=NULL) { if(tmp->data > (tmp->left)->data && tmp->data< (tmp->right)->data) { bool ans1=checkBST(tmp->left); bool ans2=checkBST(tmp->right); if(ans1 && ans2) return true; else return false; } } else if(tmp->left==NULL && tmp->right!=NULL) { if(tmp->data < (tmp->right->data)) return checkBST(tmp->right); else return false; } else if(tmp->left!=NULL && tmp->right==NULL) { if(tmp->data > (tmp->left->data)) return checkBST(tmp->left); else return false; } return true; }
vivek_23 Consider the below 2 types of trees, you will know where you went wrong.
Case 1 :
20 / \ 10 2Case 2:
18 / \ 8 20 / \ 10 30pinkRanger Alright I got it we have to find the minimum from left sub tree and the maximum from the right one Thanks!
lakhansaiteja Is it not the other way? minimum from right sub tree must be greater than root and maximum from left subtree must be less than root
noorulh06 Got it. thanks a lot.
lovesssandy Queue ino=new LinkedList(); boolean checkBST(Node root) { inorder(root); int[] arr = ino.stream().mapToInt(i->i).toArray();//convert ArrayList to primitive int array int[] brr = ino.stream().mapToInt(i->i).toArray(); //ArrayList brr=new ArrayList(arr); Arrays.sort(arr); /* for(int i:arr) System.out.print(i+","); System.out.println(""); for(int i:brr) System.out.print(i+",");*/ if(Arrays.equals(arr,brr)) return true; else return false; } void inorder(Node root) { if(root==null) return; inorder(root.left); ino.add(root.data); inorder(root.right); }
uziemblo Note, I haven't seen your code but here's a tip:
You need to also think about all previous values higher in the tree, and not just the the current node, and the top of the left and right subtrees.
WanderingFreak [deleted]Ignis_Qui_Vir [deleted]
roshanbasu11 no need for a traversal. Take the node->data of each node directly from the vector values given in private. Rest logic is spot on. Did the same :)
cameronellis711 This is great! I coded the solution to this problem in accordance with your comment!
prevVal = -1 resultVal = 1 def check_binary_search_tree_(root): inOrder(root) if resultVal == 1: return True elif resultVal == 0: return False # perform an in order traversal def inOrder(root): if root is None: return else: inOrder(root.left) global prevVal if prevVal < root.data: prevVal = root.data else: global resultVal resultVal = 0 return inOrder(root.right)
dannysiu392005 My original solution is:
def inOrder(root, stack=[]): if root.left: inOrder(root.left, stack) stack.append(root.data) if root.right: inOrder(root.right, stack) def check_binary_search_tree_(root): stack = [] inOrder(root, stack) length = len(stack) for i in range(length-1): if stack[i] >= stack[i+1]: return False return True
With your comment, I coded the following solution in python3:
flag = True pre = -1 # As all data are >= 0 so set pre = -1 def inOrder(root): global flag, pre if root.left: inOrder(root.left) if pre < root.data: pre = root.data else: flag = False return if root.right: inOrder(root.right) def check_binary_search_tree_(root): inOrder(root) global flag return flag
gschoen I did a similar thing (except that the list was in descending order). My recursive algorithm had a flaw that appeared to be too difficult to waste time fixing.
Note that I am more used to C so I didn't bother with the C++ libraries.struct List { int data; List *next; }; List *makeDescendingList(Node *head, List *list) { List *newListNode; if (head == NULL) { return list; } else { list = makeDescendingList(head->left, list); newListNode = new(List); newListNode->data = head->data; newListNode->next = list; return makeDescendingList(head->right, newListNode); } } bool isDescendingList (List *list) { while (list != NULL) { if (list->next != NULL && list->data <= list->next->data) { return false; } list = list->next; } return true; } bool checkBST(Node* root) { return isDescendingList(makeDescendingList(root, NULL)); }
a_anofriichuk You can just perform DFS and check if data is in ascending order. No additional data structures/parameters needed. Just one static variable (yep, I am a C programmer :))
bool checkBST(Node* root) { static int last_visited = -2; if (!root) { return true; } if (!checkBST(root->left)) { return false; } if (root->data <= last_visited) { return false; } last_visited = root->data; if (!checkBST(root->right)) { return false; } return true; }
mukeshkhod0001 i tried same thing but many test cases fails... help me to come out plz.
San26 [deleted]manjotmb20 I also did the same but some test cases are not working .Here my code- bool func(vector v) { int count=0; for(int i=0;i v; if(root==NULL) return true; if(root!=NULL) { checkBST(root->left); v.push_back(root->data); checkBST(root->right); } return func(v);
}
TheBloodMage You want this...
static int min = -1; static boolean flag = true; public static void inOrder(Node root){ if(root.left != null){ inOrder(root.left); } if(root.data <= min){ flag = false; } min = root.data; if(root.right != null){ inOrder(root.right); } } boolean checkBST(Node root) { inOrder(root); return flag; }
Arun_DMan [deleted]
jeganbabu did the same dude !!!!!! 2 cases failed in recursion,didn't know the reason and sample input was also confusing and accidentally i reached this solution while understanding the sample input ... ;)
AButrym [deleted]
i_am_malav You don't need to create list or array while doing inorder traversal. The whole point is to compare current and last element, if last elment is greater or equal to current return false. Just use one wrapper int, or Integer static variable to keep track of last visited.
vivek_23 But its not always true.
Consider this case:
18 / \ 8 20 / \ 10 30arasouli91 This would return false. Inorder 8 -> 18 -> 10
18 > 10
As long as the last element is the last elemented "visited" and not last element passed by.
vivek_23 Yes, but as long as we return max values from left subtrees and min values from right subtrees and make sure they follow the rule.
arasouli91 I didn't do that. I just did inorder traversal recursively and made sure it was all ascending order. Passed all cases.
vivek_23 Mine is also a similar idea.
yansiverio I think you can improve your space complexity only using a variable and comparing current node with his prev node.
sanskarsharma Was able to solve it because of your comment. thanks a lot. Here's my code.
static ArrayList<Integer> list = new ArrayList<Integer>(); boolean checkBST(Node root) { inOrder(root); for(int i = 1; i< list.size(); i++){ if(list.get(i)<=list.get(i-1)) return false; } return true; } void inOrder(Node root){ if(root == null) return; inOrder(root.left); list.add(root.data); inOrder(root.right); }
ElizaW Did the same thing.
arungupta21 I did the same. But it's not working.
Here is my code. Can you review it please?
vector <int> inorder_nodes; void Traverse_Inorder(Node *root) { if(root->left != NULL) Traverse_Inorder(root->left); inorder_nodes.push_back(root->data); if(root->right != NULL) Traverse_Inorder(root->right); } bool checkBST(Node* root) { bool result=true; Traverse_Inorder(root); for (int i = 0; i < inorder_nodes.size(); i++) { if(inorder_nodes[i] > inorder_nodes[i+1]) { result = false; break; } } return result; }vivek_23 Try this
vector <int> inorder_nodes; void Traverse_Inorder(Node *root) { if(root == NULL) return; if(root->left != NULL) Traverse_Inorder(root->left); inorder_nodes.push_back(root->data); if(root->right != NULL) Traverse_Inorder(root->right); } bool checkBST(Node* root) { Traverse_Inorder(root); for (int i = 0; i < inorder_nodes.size()-1; i++){ if(inorder_nodes[i] >= inorder_nodes[i+1]) return false; } inorder_nodes.clear(); return true; }
Zendist You should really explain how you generate the tree from input, so people can test their solutions locally as well.
LordTao I must agree. Not knowing how the tree was constructed based on the input - how it sets the root etc, made it difficult for me. Perhaps it was explained in a previous challenge somewhere but I did not find that.
aluque To those of you having issues with simple recursive code that just checks if the children are less/greater than the current node...
Right now, as you recurse down the tree you're going to only check if the children are "valid" with respect to their parent. But consider the following tree:
3 / \ / \ 2 6 / \ / \ 1 4 5 7
You'll notice that 4 > 2 BUT 4 > 3. The number 4 should be on the right side of the tree. If you wanted it to be more like a BST it should actually look like:
3 / \ / \ / \ 2 6 / \ / \ 1 4 / \ 5 7 / 4
As a result, you'll want to make sure that on a given call of your function, you know what upstream "min" and "max" to compare against. Eg; with node "4" we know that the "max" on the left subtree is "3" (the root). The "min" is "1". Now, it might be tempting to do an in-order traversal of the tree to find the allowable min/max for each node. But it's simpler if you don't allow duplicates in your tree.
On a given node, left children must be at least 1 less than the current node. Right children must be at least 1 greater than the current node. We can start with a left-most bound of the smallest representable integer and a right-most bound of the largest representable integer.
Below is a super minimal solution that implements this concept.
#include <climits> bool checkNode(Node* n,int min,int max) { if (!n) return true; //leaf, don't disqualify if (n->data < min || n->data > max) return false; return checkNode(n->left,min,n->data -1) && checkNode(n->right,n->data+1,max); } bool checkBST(Node* root) {return checkNode(root,INT_MIN,INT_MAX);}
Kunal07 Finally I got my mistake!!
jckarlos921 Easy approach with recursion:
boolean checkBST(Node root) { return checkBST(root, Integer.MIN_VALUE, Integer.MAX_VALUE); } boolean checkBST(Node root, int min, int max) { if (root == null) return true; if (root.data <= min || root.data >= max) return false; if (!checkBST(root.left, min, root.data) || !checkBST(root.right, root.data, max)) return false; return true; }Serafina This is clean and easy to understand!
jckarlos921 Thank you!
dg_12345 What is min value and max value here?
shivisharma Its min and max range of integer
scarletdenizen You can change the last if condition via DeMorgan's law to make this even simpler!
boolean checkBST(Node root, int min, int max) { if (root == null) return true; if (root.data <= min || root.data >= max) return false; return checkBST(root.left, min, root.data) && checkBST(root.right, root.data, max)); }
randypfohl This was a completely underappreciated code snippet. Good stuff.
wsun211 Wow thanks! I wrote it in Python and it worked for all test cases!
def check_binary_search_tree_(root): return checkBST(root, -1, 10001) def checkBST(root, Min, Max): if not root: return True if root.data <= Min or root.data >= Max: return False return checkBST(root.left, Min, root.data) and checkBST(root.right, root.data, Max)
timnosov really nice! I think Python's chain comparisons are underappreciated:
def check_node(node, Min, Max): if not node: return True if Min < node.data < Max: return check_node(node.left, Min, node.data) and check_node(node.right, node.data, Max) return False
hughesj919 Indeed.
The python one-liner:
def check_binary_search_tree_(root, left = float('-inf'), right = float('inf')): return not root or check_binary_search_tree_(root.left, left, root.data) and left < root.data < right and check_binary_search_tree_(root.right, root.data, right)
popovitsj Not bad. You should move your
left < root.data < rightcondition to the left for performance though.
lijubjohn This code will fail if there is a single node tree with value as Integer.MIN_VALUE or Integer.MAX_VALUE
Mothi @jckarlos921 Its failing for 7th test case.. But I have the same solution too... Even in forums the same approach is used.. U have any idea ?
ashish4rawat Love your answer and love you also
ashish_manral09 Short and simple Java code:
boolean checkBST(Node root) { return checkBSTHelper(root, Integer.MIN_VALUE, Integer.MAX_VALUE); } boolean checkBSTHelper(Node root, int low, int high) { if(root == null) return true; return root.data > low && root.data < high && checkBSTHelper(root.left, low, root.data) && checkBSTHelper(root.right, root.data, high); }
Mingling94 Super elegant
amitvarghese2011 same here bro..but it is giving compilation error..no inorder function found
ashish_manral09 hey bro, there is no inorder keyword here - are you sure?
amitvarghese2011 Yeah bro its because they have the inbuilt code in which inorder has to be called.. so sick!!
karthickpdy As a simple solution without much complications I did inorder traversal of the tree and checked if the elements are in sorted order.
void inorder(Node *root,vector<int> &a){ if(root){ inorder(root ->left,a); a.push_back(root -> data); inorder(root ->right,a); } } bool checkBST(Node* root) { vector<int> a; inorder(root,a); bool found = true; for(int i = 0 ; i < a.size() - 1; i++ ){ if(a.at(i) >= a.at(i+1)){ found = false; break; } } return found; }
coder08122014 nice solution bro...keep it up!
Twinx I am stuck at test cases 1,2,5,6,11 and 13. I am trying to check if the left sub nodes are smaller than the current and the right subnodes are greater than the current in a recursive way. If anyone has gone through the same, could you help me out?
dantes_johnAsked to answer That should work if you are doing this for all nodes. Try checking if you are doing this for all nodes including subnodes, not just root. It might be sub-optimal though.
dantes_johnAsked to answer For completeness, I used a different approach. Think types of traversal and ordering.
Twinx I had changed my methodology midway and did exactly what you suggested and got through all test cases but I'd still like to know what was wrong in the first way I came up with.
It went like this. checkBST calls a helper function check with parameters root and a value equal to 0. The check function returns val as it is for NULL root, and increments val if the subnode is greater for left subnode. After this it recursively calls itself for the left subnode sending the left subnode and val also as a parameter. Similarly for the right side. The function returns val which is checked for 0 in the original checkBST.
dantes_john Ummm .. 1. When you visit the nodes that are left of the root, do you inspect all nodes (even the right nodes of subnodes), to find the max? 2. When checking the right subnodes, are you initializing the value to a high-value (not 0) since you are looking for min?
Twinx I am not finding the maximum of minimum. I'm just verifying whether the left and right are smaller/larger respectively. Here is the code.
int check(Node* root,int val) { if(root==NULL) return val; if(root->left) { if(root->left->data >= root->data) val++; else val+=check(root->left,val); } if(root->right) { if(root->right->data <= root->data) val++; else val+=check(root->right,val); } return val; } bool checkBST(Node* root) { int i=check(root,0); if(i==0) return true; else return false; }
dantes_john But won't that miss the case where there is a right node to a left node to the root that has a value greater than the root, which violates the rule that all nodes to the left of root should be less than root?
Twinx Since it is recursive, every subnode will be explored for its right and left correct?
pmtyim Root = 100, Left = 50, Right = NULL On left node: Left = 40, Right = 200
Your code fails right on this left node.
Twinx Ohh!! Got it. Thanks a lot, all of you! :) Feel silly now.
AkashPatra94 In BST left subtree can not have a value larger than the root itself.
shaafooAsked to answer i searched for the biggest item in the left tree and the smallest item in the right tree and compared them to the root. and did that in a recursive way for all sub nodes
rahulsel My Logic to the program includes traversing the tree in Inorder so that we get the values in ascending Order and check if the list has duplicates or elements in descending order.
vector<int>v; void inorder(Node* root){ if(root){ inorder(root->left); v.push_back(root->data); inorder(root->right); } } bool checkBST(Node* root) { inorder(root); for(int i=0;i<v.size()-1;i++){ if(v[i]>=v[i+1])return false; } return true; }
Dead_Skull_7 Inorder traversal of a BST is always a sorted order. cakewalk for 30 pts!
Sort 347 Discussions, By:
Please Login in order to post a comment