How do you validate a binary search tree?

by

Actually that is the mistake everybody does in an interview.

Leftchild must be checked against (minLimitof node,node.value)

Rightchild must be checked against (node.value,MaxLimit of node)

IsValidBST(root,-infinity,infinity);

bool IsValidBST(BinaryNode node, int MIN, int MAX) 
{
     if(node == null)
         return true;
     if(node.element > MIN 
         && node.element < MAX
         && IsValidBST(node.left,MIN,node.element)
         && IsValidBST(node.right,node.element,MAX))
         return true;
     else 
         return false;
}

Another solution (if space is not a constraint):
Do an inorder traversal of the tree and store the node values in an array. If the array is in sorted order, its a valid BST otherwise not.

More Related Contents:

  1. In Order Successor in Binary Search Tree
  2. How to create the most compact mapping n → isprime(n) up to a limit N?
  3. Reverse the ordering of words in a string
  4. How to create the most compact mapping n → isprime(n) up to a limit N?
  5. Hash table runtime complexity (insert, search and delete)
  6. Data structures for loaded dice?
  7. How to implement a queue using two stacks?
  8. Heap vs Binary Search Tree (BST)
  9. Store the largest 5000 numbers from a stream of numbers
  10. Computing set intersection in linear time?
  11. How to delete in a heap data structure?
  12. What is the difference between tree depth and height?
  13. How Do I Choose Between a Hash Table and a Trie (Prefix Tree)?
  14. insert, delete, max in O(1)
  15. O(klogk) time algorithm to find kth smallest element from a binary heap
  16. Skip List vs. Binary Search Tree
  17. Algorithm for autocomplete?
  18. What is the advantage to using Bloom filters?
  19. Why does Dijkstra’s algorithm use decrease-key?
  20. Finding height in Binary Search Tree
  21. How can I return an array of struct in solidity?
  22. Search a sorted 2D matrix [duplicate]
  23. The intersection of all combinations of n sets
  24. Why increase pointer by two while finding loop in linked list, why not 3,4,5?
  25. Why are hash table expansions usually done by doubling the size?
  26. Algorithm for merging two max heaps?
  27. What are probabilistic data structures?
  28. How to find the number of different shortest paths between two vertices, in directed graph and with linear-time?
  29. Why is vector array doubled?
  30. How to apply binary search O(log n) on a sorted linked list?

Leave a Comment