is a Binary Tree also a Binary Search Tree?

Question

Write an algorithm to verify if a Binary Tree (BT) is a Binary Search Tree (BST).

Definitions

 

 BT: A binary tree  in computer science is a tree data structure in which each node has at most two child nodes, usually distinguished as "left" and "right".

BST: A binary search tree (BST) (aka ordered or sorted binary tree) in computer science is a node-based binary tree data structure having following properties:^[1]

1. The left subtree of a node contains only nodes with keys less than the node's key.
2. The right subtree of a node contains only nodes with keys greater than the node's key.
3. Both the left and right subtrees must also be binary search trees.

Generally, the information represented by each node is a record rather than a single data element. However, for sequencing purposes, nodes are compared according to their keys rather than any part of their associated records.

Solutions

 

1. An in-order traversal of the binary tree should  yield a sorted list of node keys.

2. Write a function (iterative/recursive) to verify the three basic properties of a BST
 as described above.

References

 

1. CSLibrary Stanford
    This discusses many interesting functions on binary trees and binary search trees: Lookup(), Insert(), Delete(), NoOfNodes(), MaxDepth(), MinValue(), PathSum(), Mirror(), doubleTree(), sameTree(), countTrees()


2. UCB Video Lecture on Binary Search Trees





3. UCB Video Lecture Series on Data Structures