• 0

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