- Trees: Is This a Binary Search Tree?
- Discussions
Trees: Is This a Binary Search Tree?
Trees: Is This a Binary Search Tree?
+ 0 comments - Python 3
- an in order traversal of the tree and save the order indexes into
data_list
- set new property
ancestor
into node objects, which is somewhat cheating because may only be add in dynamic language such as Python, but can also be implement in other static languages by using data structure like dictionaries / hashmaps - check
data_list
is in order, and also no duplication (by checking length)
from collections import defaultdict def checkBST(root): node_traversed_counts = defaultdict(int) current_node = root current_node.ancestor = None data_list = [] while node_traversed_counts[root] < 3: # new node if not node_traversed_counts.get(current_node): node_traversed_counts[current_node] += 1 # is leaf node if not current_node.left and not current_node.right: data_list.append(current_node.data) current_node = current_node.ancestor # is not leaf node else: if current_node.left: current_node.left.ancestor = current_node current_node = current_node.left # node having been traversed before else: node_traversed_counts[current_node] += 1 if node_traversed_counts[current_node] == 2: data_list.append(current_node.data) if current_node.right: current_node.right.ancestor = current_node current_node = current_node.right continue current_node = current_node.ancestor return data_list == sorted(data_list) and len(set(data_list)) == len(data_list)
+ 0 comments This one is really bad in c. Not given any starter structures for tree. Not given any input scanning.
Due to this, the best implementation is to just read input and compare the values in order. Allocating memory to put this in a tree would be a waste.
if values are out of order, ret "No".
+ 0 comments python has same input for two different scenarios but show different expected output
+ 0 comments bool solve(Node* root, int mini, int maxi){ if(root==NULL){ return 1; } if(root->data > mini && root->data< maxi){ bool a=solve(root->left, mini, root->data); bool b=solve(root->right, root->data, maxi); return a && b; } else{ return 0; } }
bool checkBST(Node* root) { int mini=INT_MIN; int maxi=INT_MAX; return solve(root, mini, maxi); }
+ 1 comment This problem is totally broken with Java 8. Boilerplate is hidden, but broken.
Sort 792 Discussions, By:
Please Login in order to post a comment