Difference between binary tree and binary search tree

Question

Can anyone please explain the difference between binary tree and binary search tree with an example?

Burnie

Answer 1

Binary tree: Tree where each node has up to two leaves

  1
 / \
2   3

---

Binary search tree: Used for searching. A binary tree where the left child contains only nodes with values less than the parent node, and where the right child only contains nodes with values greater than or equal to the parent.

  2
 / \
1   3

Squarely

@pete: It's a conceptual thing, you won't necessarily ever actually make one that is completely unconstrained. However, there are lots of non-search binary trees that are special in some other way, e.g. binary heaps. – Squarely

@pete birary trees do not necessarily have to contain comparable data, many (non search) binary trees are used for parsing algebraic expression, binary tree is perfect t write a infix notation parser, by placing the operator as node(s) and numerical values as leafs – Myoglobin

@JBoy: They're not going to be binary trees in that case though. (e.g. unary operators can't have two children.) I really can't think of a practical use case for unconstrained binary trees, that's why I made that comment. – Squarely

@Mehrdad A binary tree has one or two children per node. Expression trees are a perfect example. A binary search tree also has one or two children per node, unless it happens to be full, which can only happen with certain numbers of elements. – Octangular

@JBoy: No, expression trees are actually the perfect counterexample. They can have any number of children, not just up to 2 (say, f(x,y,z)), unless you're artificially limiting them for no reason. Again, I can't think of anything that's naturally limited to 2 children. (As a side note, note that unary operator nodes never have 2 children, whereas in a binary tree any node is given 2 child slots that in general can be filled.) – Squarely

@Mehrdad IMHO, the image for the binary tree might be a little misleading (as you have specified the nodes with numbers). People might start comparing it to the other example. I don't exactly know how to provide one here, but I suggest using some character that shows any value can be placed there. – Subbasement

Create a binary tree, carry out a sort operation on it - think called treesort - then it becomes a Binary Search Tree ; can search 1000 items with only 10 comparisons, so very fast. However sorting is time consuming operation, so only do it once at the beginning. – Milne

A min-heap and max-heap can be represented using a "non-search" binary tree. @pete – Capone

@Ali: I'm guessing you missed my reply to his comment just underneath... – Squarely

For binary trees, does the left child have to precede the right child in terms of their key-values (i.e. numeric, lexigraphically) as shown in the example? Can the key value of the left child be 3 and right child be 2? – Devoirs

@NoName: Nope it doesn't. The only constraints are the ones I've explicitly stated. – Squarely

@Mehrdad is there any implementation of binary tree? (not binary search tree) because I'm struggling with it and didn't find any example of it. Every one is giving the binary search tree code. – Eveland

@AsifMushtaq: Sorry I never replied, I think there isn't one because... what would its use case be, and what would be the contribution of an existing implementation? Like I wrote earlier, I don't know of any use case for plain unconstrained binary trees, and in some languages they're already trivial to represent anyway (e.g. [left, value, right] in Python). – Squarely

There are binary search trees which don't necessarily obey the local ordering criterion left <= node <= right. If the size of the discriminator set is in the range of the reserved memory you can use a global compare which automatically protects you from degeneration, and the tree will be "mostly balanced" (no leaf deeper log(N)) – Fernandina

@Vroomfondel: What kinds of trees are you thinking of in particular? I'm guessing they might be binary trees used for searching, but I think the term "binary search tree" specifically refers to those that obey the ordering criterion... at least/especially in introductory computer science. (Though I wouldn't really call it "local", since it applies to the whole left and right subtrees?) – Squarely

@Squarely Here you can see a scheme in ASCII art right at the top: in this exemplary tree you have allowed ranges for every tree level (marked with |) shrinking with every level down. You can vertically reorder nodes in this tree and still get a tree of the same property. Of course this works only for special cases and in searching you can't early-out but have to search the whole structure down. In my case I use it for a single-threaded memory allocator which has an easy time merging freed blocks due to this. – Fernandina

@Squarely PS: trees which are constructed with this property have a hard worst case depth of log(n) and are therefore always "mostly balanced". I don't know if they have a name (or if they are handled as trees at all in the literature) and would be grateful if you can provide me a pointer of someone treating this type in a more academic approach. – Fernandina

@Vroomfondel: Interesting. I know nothing about these trees unfortunately, but I don't expect they're called BSTs. Might be worth asking on CS.SE though, if you'd like to see if anyone knows more about them. – Squarely

Answer 2

Binary Tree is a specialized form of tree with two child (left child and right Child). It is simply representation of data in Tree structure

Binary Search Tree (BST) is a special type of Binary Tree that follows following condition:

1. left child node is smaller than its parent Node
2. right child node is greater than its parent Node

Kathernkatheryn

These conditions are not sufficient. The entire left subtree must contain no keys only less than the parent's, and the entire right subtree must contain nodes greater. – Octangular

@EJP can you elaborate your comment please? what do you mean by entire subtree? you mean the all values of subtree should be less than to root on the left side? and all the values should be greater than root value on the right side? – Eveland

Following the second link, read the section on "Verification" and it will be clear. – Ofilia

Answer 3

A binary tree is made of nodes, where each node contains a "left" pointer, a "right" pointer, and a data element. The "root" pointer points to the topmost node in the tree. The left and right pointers recursively point to smaller "subtrees" on either side. A null pointer represents a binary tree with no elements -- the empty tree. The formal recursive definition is: a binary tree is either empty (represented by a null pointer), or is made of a single node, where the left and right pointers (recursive definition ahead) each point to a binary tree.

A binary search tree (BST) or "ordered binary tree" is a type of binary tree where the nodes are arranged in order: for each node, all elements in its left subtree are less to the node (<), and all the elements in its right subtree are greater than the node (>).

    5
   / \
  3   6 
 / \   \
1   4   9    

The tree shown above is a binary search tree -- the "root" node is a 5, and its left subtree nodes (1, 3, 4) are < 5, and its right subtree nodes (6, 9) are > 5. Recursively, each of the subtrees must also obey the binary search tree constraint: in the (1, 3, 4) subtree, the 3 is the root, the 1 < 3 and 4 > 3.

Watch out for the exact wording in the problems -- a "binary search tree" is different from a "binary tree".

Garrido

@GabrielStaples Added tree structure. – Plummet

Answer 4

As everybody above has explained about the difference between binary tree and binary search tree, i am just adding how to test whether the given binary tree is binary search tree.

boolean b = new Sample().isBinarySearchTree(n1, Integer.MIN_VALUE, Integer.MAX_VALUE);
.......
.......
.......
public boolean isBinarySearchTree(TreeNode node, int min, int max)
{

    if(node == null)
    {
        return true;
    }

    boolean left = isBinarySearchTree(node.getLeft(), min, node.getValue());
    boolean right = isBinarySearchTree(node.getRight(), node.getValue(), max);

    return left && right && (node.getValue()<max) && (node.getValue()>=min);

}

Hope it will help you. Sorry if i am diverting from the topic as i felt it's worth mentioning this here.

Toluol

Either the left or the right subtree can be empty. Your code doesn't handle that case correctly. – Octangular

@Octangular Also there are binary search trees which don't obey a local ordering criteria and are still binary search trees (with optimality and all). – Fernandina

Answer 5

Binary Tree stands for a data structure which is made up of nodes that can only have two children references.

Binary Search Tree (BST) on the other hand, is a special form of Binary Tree data structure where each node has a comparable value, and smaller valued children attached to left and larger valued children attached to the right.

Thus, all BST's are Binary Tree however only some Binary Tree's may be also BST. Notify that BST is a subset of Binary Tree.

So, Binary Tree is more of a general data-structure than Binary Search Tree. And also you have to notify that Binary Search Tree is a sorted tree whereas there is no such set of rules for generic Binary Tree.

Binary Tree

A Binary Tree which is not a BST;

         5
       /   \
      /     \
     9       2
    / \     / \
  15   17  19  21

Binary Search Tree (sorted Tree)

A Binary Search Tree which is also a Binary Tree;

         50
       /    \
      /      \
     25      75
    /  \    /  \
  20    30 70   80

Binary Search Tree Node property

Also notify that for any parent node in the BST;

• All the left nodes have smaller value than the value of the parent node. In the upper example, the nodes with values { 20, 25, 30 } which are all located on the left (left descendants) of 50, are smaller than 50.

• All the right nodes have greater value than the value of the parent node. In the upper example, the nodes with values { 70, 75, 80 } which are all located on the right (right descendants) of 50, are greater than 50.

There is no such a rule for Binary Tree Node. The only rule for Binary Tree Node is having two childrens so it self-explains itself that why called binary.

Encage

Can we implement Simple Binary Tree? is there any implementation available? and what is the use of this tree? – Eveland

@UnKnown You can use the Binary Search Tree is for sort and search. You can find the implementation of Binary Search Tree here: github.com/bzdgn/data-structures-in-java/blob/master/src/… – Encage

I know about that but is there any existence of Simple Tree or Simple Binary Tree? or any implementation of Simple Binary Tree? – Eveland

There is no point to use that but you can add arbitrary Node instances to the root and to the children. – Encage

Answer 6

A binary search tree is a special kind of binary tree which exhibits the following property: for any node n, every descendant node's value in the left subtree of n is less than the value of n, and every descendant node's value in the right subtree is greater than the value of n.

Transition

Answer 7

Binary tree

Binary tree can be anything which has 2 child and 1 parent. It can be implemented as linked list or array, or with your custom API. Once you start to add more specific rules into it, it becomes more specialized tree. Most common known implementation is that, add smaller nodes on left and larger ones on right.

For example, a labeled binary tree of size 9 and height 3, with a root node whose value is 2. Tree is unbalanced and not sorted. https://en.wikipedia.org/wiki/Binary_tree

For example, in the tree on the left, A has the 6 children {B,C,D,E,F,G}. It can be converted into the binary tree on the right.

Binary Search

Binary Search is technique/algorithm which is used to find specific item on node chain. Binary search works on sorted arrays.

Binary search compares the target value to the middle element of the array; if they are unequal, the half in which the target cannot lie is eliminated and the search continues on the remaining half until it is successful or the remaining half is empty. https://en.wikipedia.org/wiki/Binary_search_algorithm

A tree representing binary search. The array being searched here is [20, 30, 40, 50, 90, 100], and the target value is 40.

Binary search tree

This is one of the implementations of binary tree. This is specialized for searching.

Binary search tree and B-tree data structures are based on binary search.

Binary search trees (BST), sometimes called ordered or sorted binary trees, are a particular type of container: data structures that store "items" (such as numbers, names etc.) in memory. https://en.wikipedia.org/wiki/Binary_search_tree

A binary search tree of size 9 and depth 3, with 8 at the root. The leaves are not drawn.

And finally great schema for performance comparison of well-known data-structures and algorithms applied:

Image taken from Algorithms (4th Edition)

Eponymy

Answer 8

• Binary search tree: when inorder traversal is made on binary tree, you get sorted values of inserted items
• Binary tree: no sorted order is found in any kind of traversal

Slave

No sorted order need be found. A binary search tree is also a binary tree. They are not mutually exclusive. BST is a proper subset of BT. – Octangular

Right, if you read closely, that is why Binary search tree explanation has - when inorder traversal is made on * binary tree * – Slave

Answer 9

A binary tree is a tree whose children are never more than two. A binary search tree follows the invariant that the left child should have a smaller value than the root node's key, while the right child should have a greater value than the root node's key.

Seddon

Answer 10

To check wheather or not a given Binary Tree is Binary Search Tree here's is an Alternative Approach .

Traverse Tree In Inorder Fashion (i.e. Left Child --> Parent --> Right Child ) , Store Traversed Node Data in a temporary Variable lets say temp , just before storing into temp , Check wheather current Node's data is higher then previous one or not . Then just break it out , Tree is not Binary Search Tree else traverse untill end.

Below is an example with Java:

public static boolean isBinarySearchTree(Tree root)
{
    if(root==null)
        return false;

    isBinarySearchTree(root.left);
    if(tree.data<temp)
        return false;
    else
        temp=tree.data;
    isBinarySearchTree(root.right);
    return true;
}

Maintain temp variable outside

Raquelraquela

Either subtree can be null. Your algorithm doesn't handle that case correctly. – Octangular

Answer 11

A tree can be called as a binary tree if and only if the maximum number of children of any of the nodes is two.

A tree can be called as a binary search tree if and only if the maximum number of children of any of the nodes is two and the left child is always smaller than the right child.

Unclassified

Answer 12

In a Binary search tree, all the nodes are arranged in a specific order - nodes to the left of a root node have a smaller value than its root, and all the nodes to the right of a node have values greater than the value of the root.

Beardless

Answer 13

In a binary tree, each node has 2 child nodes the left node and the right node. A Binary Search tree is a special kind of tree in which the nodes are sorted, the left node is smaller than the parent node and the left node is bigger than the parent node. The binary tree allows duplicate values, Binary search tree doesn't allow duplicate values also carrying out any kind of operation is faster in Binary search tree than in Binary tree since BST is sorted

Matronymic

As it’s currently written, your answer is unclear. Please edit to add additional details that will help others understand how this addresses the question asked. You can find more information on how to write good answers in the help center. – Good

Answer 14

A binary tree is a tree, in which each node can have at most 2 children.

A binary search tree is a further modification of this, giving a certain relationship to the parent and the two children. Since, there are only two children, i.e., left and right child; the relation is defined as follows:

Left Child <= Parent <= Right Child

It is actually, that simple.

Emmi