Different Traversals:
The following methods can be used to navigate the Binary Search Tree:
Pre-order Traversal
In-order Traversal
Post-order Traversal
A binary search tree is primarily used because it increases an array's functional range.
A data type called an array stores data points in orderly succession. Because each element in the array has an index, it is possible to quickly access them by using, for instance, A[0] to get the first element or A[103] to get the 104th element. The access time for arrays is either constant time or O(1).
The downside and upside of an array, though, is indexing.
The index of the elements in positions 50 through 100 would need to be updated (by adding 1) if you wanted to add an item to the array's existing length of 100. Behind the scenes, this occurs. Adding a new element to the front of an array would be the absolute worst case. O(n) time complexity for linear time operation.
All elements that come after the newly inserted element must be re-indexed when the aforementioned code is run. Although this O(n) time operation is not particularly slow, it can be outperformed by another data structure.
A list of the data elements in a binary search tree is not kept as an index. Instead, it keeps track of each element's location using its implicit structure (to the left or right of each node). Thus, insertion and deletion take place in O (log n) time, which is a logarithmic time unit.
Time Complexity
Insert, search, and delete operations can frequently be completed in O(log n) time, where n is the number of nodes in the tree. This is made possible by the characteristics mentioned above. However, the worst-case time complexity for these operations is O(n) when the tree loses balance.
Space Complexity
The average and worst-case space complexity of a binary search tree is O(n).
Conclusion
A binary tree is a tree in which each node has a maximum of two children and a minimum of zero children. A key or id is used to identify each node.
A binary search tree is a binary tree in which the nodes are sorted following a single rule: all nodes on a node's left subtree have keys that are less valuable than the node, while all nodes on the right subtree have more valuable keys.
As a result, elements stored in the tree can be retrieved relatively quickly because each node key comparison enables the tree's half to be discarded. The term for this is binary search.
To get a detailed idea about it you should go for Tutort Academy's , DSA and System Design course.
Comments