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

Video Lectures on Statistical Hypothesis Testing

1. Basics of Hypothesis testing

2. Hypothesis Test 

List fo Videos on NoSQL Database MongoDB

1. Installation and Introduction to MongoDB



2. O'Reilly Webcast: Introduction to MongoDB

 

3.Introduction to MongoDB




4. Inside MongoDB







5. Will Shulman (MongoLab) Talk on MongoDB : It's Not Just About Big Data






6.  MongoDB Schema Design





7.  O'Reilly Webcast: A MongoDB Optimization Primer for Indexing






8. O' Reilly Webcast : Scaling With MongoDB





9.  O' Reilly Webcast : Sharding



10.   MangoDB Internals

11.  MongoDB and Python

12.  Introduction to Using MongoDB and Spring Data on Cloud Foundary





13.  Building Mobile Backend  with MongoDB






14. MongoDB Backups using Replica Sets

15. Scaling With MongoDB

Introduction to Predictive Analytics

Everyone is highly curios to have a glimpse at the future. A peek into the future not only provides excitement in general but also helps to in proper planning and laying out import strategies. At the minimal, future predictions give us an opportunity to be prepared for the bad times and minimize the losses.  For example,  a tool that helps a human resource manager to predict the employees who are at the risk of seeking voluntary termination from the organization is immensely helpful. This helps the manager in taking proper actions to retain high performing employees and minimize losses by reducing operating costs of the organization.

Development of methodologies and tools to predict future are of utmost importance.  Predictive analytics is one such field of study at the junction of statistics, data mining, and machine learning that aims to provide future insights into various domains.


What is predictive analytics?

It is a process of analyzing historical and current facts to get an insight into future risks,  events, and trends.  Its goal is to generate actionable items for an end user to address future needs.  It finds its use in all the field of sciences, marketing, healthcare, insurance, telecommunications, and other domains.


Difference from the state-of-the-art Business Intelligence practices

The state-of-the-art Business intelligence methods generate static reports from the historical data. For example, given a repository of sales transactions, a BI software generates different kinds of reports, in the form of documents, visual charts or spreadsheets, based on  demographics, time,  product categories and other criteria. This helps an end user to analyze the historical data and discover the factors that led to the observed sales data.  In BI,  onus lies with the end user to discover future trends and events from the reports. On the contrary, predictive analytics automatically generates the future trends and events by analyzing the historical data.

References
1. Wikipedia Article
2. Dean Abbott Blog
3. Forbes Article
4. Predictive analytics with data mining

Products
1. Oracle Data Mining and Predictive Analytics
2. IBM's SPSS
3. SAS
4. We Predict
5. Revolutionanalytics