Difference Between Binary Tree and Binary Search Tree
And it is going to take almost only 1 minute for you to read this post.
But there are so many tree types in the literature that might blow your mind up.
So what is the difference?
Let’s take a look at it.
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 (>). 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”.
In a basic description, we can say that:
Binary tree: Tree where each node has up to two leaves
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.