What is a Binary Search Tree?
A Binary Search Tree is a binary tree where each node contains a key and an optional associated value. It allows particularly fast lookup, addition, and removal of items.
The nodes are arranged in a binary search tree according to the following properties:
-
The left subtree of a particular node will always contain nodes with keys less than that node’s key.
-
The right subtree of a particular node will always contain nodes with keys greater than that node’s key.
-
The left and the right subtree of a particular node will also, in turn, be binary search trees.
Time Complexity
In average cases, the above mentioned properties enable the insert, search and deletion operations in time where n is the number of nodes in the tree. However, the time complexity for these operations is in the worst case when the tree becomes unbalanced.
Space Complexity
The space complexity of a binary search tree is in both the average and the worst cases.
Types of Traversals
The Binary Search Tree can be traversed in the following ways:
- Pre-order Traversal
- In-order Traversal
- Post-order Traversal
The pre-order traversal will visit nodes in Parent-LeftChild-RightChild order.
The in-order traversal will visit nodes in LeftChild-Parent-RightChild order. In this way, the tree is traversed in an ascending order of keys.
The post-order traversal will visit nodes in LeftChild-RightChild-Parent order.
RELATED TAGS
