is BST or not ?
Check whether the Binary tree is BST or not ?
[AMAZON] Vertical sum of nodes
Given a Binary Tree, find vertical sum of the nodes that are in same vertical line. Print all sums through different vertical lines. Examples: 1 / \ 2 3 / \ / \ 4 5 6 7 The tree has 5 vertical lines Vertical-Line-1 has only one node 4 => vertical sum is 4 Vertical-Line-2: has only one node 2=> vertical sum is 2 Vertical-Line-3: has three nodes: 1,5,6 => vertical sum is 1+5+6 = 12 Vertical-Line-4: has only one node 3 => vertical sum is 3 Vertical-Line-5: has only one node 7 => vertical sum is 7 So expected output is 4, 2, 12, 3 and 7
int isBST(struct node *root)
ReplyDelete{
if(root == NULL) return 1;
else if(root->left->value > root->value || root->right->value < root->value) return 0;
else return(isBST(root->left) && isBST(root->right))
}
Its wrong....
ReplyDeleteCounter test case :
5
/ \
2 6
/ \
1 9
Its not BST... ur code will return true.
U will have to keep a max and min of a subtree too.
@gaurav yes this code takes care of left and right child if misplaced.if you want to check if tree is correctly formed then you will have to keep track of min and max value.agreed..:)
ReplyDeleteint isBST(struct node* node, int min, int max)
ReplyDelete{
/* an empty tree is BST */
if (node==NULL)
return 1;
/* false if this node violates the min/max constraint */
if (node->data < min || node->data > max)
return 0;
return
isBST(node->left, min, node->data) &&
isBST(node->right, node->data+1, max);
}
call isBST(node,INT_MIN, INT_MAX) initially.