what is the difference between a Binary Search Tree and a Threaded Binary Tree?

Question

I mean that a binary search tree is a tree where the left child is smaller and right child is greater/equal to than the parent.

A threaded binary tree has threads. How does this makes it different?

Answer 1

In threaded binary trees, the leaves, which would have null references are replaced with references to the in-order successor (in case of right childs) or predecessor (in case of left childs) nodes. If only successor or predecessor references are used, then the tree is single threaded, if both, then it is double threaded. This makes the in-order traversal of nodes computationally cheaper.

This image (borrowed from Wikipedia) show the data structure nicely:

Please refer to the Wikipedia article for more information.

Answer 2

Comparing the two concepts is sort of like comparing apples and buffalo. :) A binary search tree is a special case of a binary search tree, in which the elements satisfy the ordering you mention--everything in the left subtree must be less than the root node, and everything in the right subtree must be greater. A threaded tree doesn't have any such restrictions, and in fact a threaded tree doesn't have to have data in the nodes that can be compared with an ordering relationship. In fact, a binary search tree is a concept that has nothing inherently to do with how the tree is implemented, while a threaded tree is only about how trees are implemented--i.e. how you set up the pointers in the tree nodes. A binary search tree can be a threaded tree if you decide to implement it that way.