Determine if a binary tree is a binary search tree
Binary tree and Binary search tree are defined as follows :
Binary tree is a tree data structure in which each node has at most two child nodes.
A binary search tree (BST) is a rooted binary tree, whose internal nodes each store a key and each have two distinguished sub-trees, commonly denoted left and right.
- The tree additionally satisfies the binary search tree property, which states that the key in each node must be greater than all keys stored in the left sub-tree, and smaller than all keys in right sub-tree.
The visualizations of binary search tree can be found here.
Logic :
- Traverse the tree in-order
- Compare the current element with the previous element
Note: This approach can not detect duplicates. We will assume all nodes in the tree have unique values.
Time complexity : O (N)
Solution :
- CTCI_6_4.5