Thursday Code Puzzler: Verification of a Binary Search Tree
Thursday is code puzzler day here at DZone. The idea is simple: solve the coding problem as efficiently as you can, in any language or framework that you find suitable.
Note: Even though there really is nothing stopping you from finding a solution to this on the internet, try to keep honest, and come up with your own answer. It's all about the participation!
Verify if the tree is a binary search tree
Do you have code puzzlers that you'd like to share with the DZone community? If so, please submit here.
Given a tree structure, provide a method that will verify whether or not it is actually a binary search tree. The Tree consists of a number of Node objects, each of which has a value and a reference to a right and left Node object.
Note that a BST is different to a standard binary tree because of the following properties :
- The leftsubtreeof a node contains only nodes with keys less than the node's key.
- The right subtree of a node contains only nodes with keys greater than the node's key.
- Both the left and right subtrees must also be binary search trees.
- There must be no duplicate nodes.
For more on Binary Search Trees, check this article on Wikipedia.
Catch up on all our previous puzzlers here.