Show Buttons
Share On Facebook
Share On Twitter
Share On Google Plus
Share On Linkdin
Share On Reddit
Contact us
Hide Buttons

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

You may also like...

Leave a Reply

Your email address will not be published. Required fields are marked *