Difference between Binary Tree and Binary Search Tree
Binary Tree Data Structure:
A tree whose elements have at most 2 children is called a binary tree. Since each element in a binary tree can have only 2 children, we typically name them the left and right children.
Binary Search Tree Data Structure (BST):
A binary search tree is a hierarchical data structure where each node has at most two children, with values ordered such that left child values are smaller and right child values are greater.
A binary Search Tree is a node-based binary tree data structure that has the following properties:
- The left subtree of a node contains only nodes with keys lesser than the node’s key.
- The right subtree of a node contains only nodes with keys greater than the node’s key.
- The left and right subtree each must also be a binary search tree.
- There must be no duplicate nodes.
Difference between Binary Tree and Binary Search Tree:
Feature | Binary Tree | Binary Search Tree ( BST ) |
---|---|---|
Definition | A tree data structure where each node can have at most two children nodes. | A binary tree in which for each node, all elements in its left subtree are less than the node, and all elements in its right subtree are greater than the node. |
Node Insertion | Nodes are inserted without any specific order. | Nodes are inserted according to their values, maintaining the BST property. |
Node Lookup/Search | No specific order; full tree traversal may be needed to find a node. | Efficient lookup using the binary search property, reducing the search space by half at each step. |
Time Complexity (average case) | O(n) for insertion, deletion, and search. | O(h) for insertion, deletion, and search, where h is height. |
Space Complexity | O(n) as it only depends on the number of nodes in the tree. | O(n) as it only depends on the number of nodes in the tree. |
Application | Used in various tree-related algorithms and data structures. | Ideal for applications where efficient search, insertion, and deletion are required, such as in databases and dictionaries |
Contact Us