[data-structures] Difference between binary tree and binary search tree

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

This question is related to data-structures tree binary-tree binary-search-tree

The answer is


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.


  • 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

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.


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.


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.


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


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.


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

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".


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

enter image description here

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.

enter image description here

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

enter image description here

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

enter image description here

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.

enter image description here

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

enter image description here

Image taken from Algorithms (4th Edition)


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.


Examples related to data-structures

Program to find largest and second largest number in array golang why don't we have a set datastructure How to initialize a vector with fixed length in R C compiling - "undefined reference to"? List of all unique characters in a string? Binary Search Tree - Java Implementation How to clone object in C++ ? Or Is there another solution? How to check queue length in Python Difference between "Complete binary tree", "strict binary tree","full binary Tree"? Write code to convert given number into words (eg 1234 as input should output one thousand two hundred and thirty four)

Examples related to tree

Tree implementation in Java (root, parents and children) Build tree array from flat array in javascript Binary Search Tree - Java Implementation Difference between "Complete binary tree", "strict binary tree","full binary Tree"? Tree view of a directory/folder in Windows? Definition of a Balanced Tree Difference between binary tree and binary search tree How to create a collapsing tree table in html/css/js? How to search JSON tree with jQuery Non-recursive depth first search algorithm

Examples related to binary-tree

Difference between "Complete binary tree", "strict binary tree","full binary Tree"? Difference between binary tree and binary search tree Heap vs Binary Search Tree (BST) C linked list inserting node at the end How to print binary tree diagram? With ' N ' no of nodes, how many different Binary and Binary Search Trees possible? How to implement a binary tree? Find kth smallest element in a binary search tree in Optimum way What are the applications of binary trees? How to find the lowest common ancestor of two nodes in any binary tree?

Examples related to binary-search-tree

Difference between binary tree and binary search tree Heap vs Binary Search Tree (BST) How to implement a binary search tree in Python? Finding height in Binary Search Tree