# [BSTq](https://github.com/omkashyap007/Binary-Search-Tree-Library/tree/master)
BSTq is a comprehensive Python library dedicated to Binary Search Trees (BSTs). Designed to work with BSTs, this library offers a wide array of functions and utilities, rather than basic functions to work with binary search trees effortlessly.
This library has lots of functions which can be used to minimize your efforts for Binary Search Trees .
## Install
```
pip install bstq
```
## Usage
```
from bstq import *
```
### Creating Binary Search Tree
The following class is used to create a BinarySearchTree and instanciate a tree object with root value of 10 .
```python
class BinarySearchTree:
def __init__(self , data , left = None, right = None) :
self.data = data
self.left = left
self.right = right
root = BinarySearchTree(10)
```
### Create Binary Search Tree from Sorted list.
You have to provide a sorted list which you will paas in the `createBSTFromSortedList` , the function will return a root of the Binary Search Tree created from the list .
```python
l = [11, 14, 36, 64, 69, 71, 83, 83] # sorted list.
root = createBSTFromSortedList(l)
print(root)
Output :
Sorted List : [11, 14, 36, 64, 69, 71, 83, 83]
64
__/ \__
14 71
/ \ / \
11 36 69 83
\
83
```
### Create Binary Search Tree With given Height .
You can use `createBSTWithHeight` function to create BST with given height.
```
bst = createBSTWithHeight(4)
print(bst)
```
```
Output :
8
______/ \_____
4 12
__/ \_ __/ \__
2 6 10 14
/ \ / \ / \ / \
1 3 5 7 9 11 13 15
```
## InOrder , PreOrder , PostOrder , LevelOrder Traversals .
There are two methods for traversals , one is class based which is specific to class and another is global method for bst.
```python
in_order = bst.inOrder() # class method
in_order = inOrder(bst) # global method
print(f"In Order : {in_order}")
pre_order = bst.preOrder() # class method
pre_order = preOrder(bst) # global method
print(f"Pre Order : {pre_order}")
post_order = bst.postOrder() # class method
post_order = postOrder(bst) # global method
print(f"Post Order : {post_order}")
level_order = bst.levelOrder() # class method
level_order = levelOrder(bst) # global method
print(f"Level Order : {level_order}")
```
```
Output :
In Order : [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15]
Pre Order : [8, 4, 2, 1, 3, 6, 5, 7, 12, 10, 9, 11, 14, 13, 15]
Post Order : [1, 3, 2, 5, 7, 6, 4, 9, 11, 10, 13, 15, 14, 12, 8]
Level Order : [8, 4, 12, 2, 6, 10, 14, 1, 3, 5, 7, 9, 11, 13, 15]
```
### List Level Order Traversal
This function gives the list of all the levels of bst .
```
level_order_list = bst.levelOrderList()
level_order_list = levelOrderList(bst)
print(level_order_list)
```
```
Output :
[[8], [4, 12], [2, 6, 10, 14], [1, 3, 5, 7, 9, 11, 13, 15]]
```
### Search in bst
```python
node = searchInBST(bst , 6)
node = bst.searchInBST(6)
print(node)
Ouput :
6
/ \
5 7
```
### Height of bst
```python
h = bst.height()
h = height(bst)
Output :
4
```
### Printing Binary Tree
You will get the most prettiest display of Binary Search Tree .
```
printBTree(bst) # global function
print(bst) # you can also use print function directly .
Output :
8
______/ \_____
4 12
__/ \_ __/ \__
2 6 10 14
/ \ / \ / \ / \
1 3 5 7 9 11 13 15
```
### Printing the Binary Search Tree Horizontally Flipped .
You cannot use the print function , you have to use `printBTree()` with inverted parameter to be True
```python
printBTree(bst , inverted = True)
Output :
1 3 5 7 9 11 13 15
\ / \ / \ / \ /
2 6 10 14
¯¯\ /¯ ¯¯\ /¯¯
4 12
¯¯¯¯¯¯\ /¯¯¯¯¯
8
```
### Invert BST
Invertes the binary search tree to its mirror image .
```python
inverted_tree = invertBST(bst)
print(inverted_tree)
8
______/ \______
12 4
__/ \__ __/ \_
14 10 6 2
/ \ / \ / \ / \
15 13 11 9 7 5 3 1
```
### Top View of BST
```python
top_view = topViewOfBST(bst)
print(top_view)
Output :
[1, 2, 4, 8, 12, 14, 15]
```
### Delete Node in BST
Gives and new node with delete bst and also deletes from the actual one.
```python
new_bst = deleteNodeInBST(bst , 6)
print(new_bst)
Output :
8
_____/ \_____
4 12
/ \ __/ \__
2 5 10 14
/ \ \ / \ / \
1 3 7 9 11 13 15
```
### Distance of Node From Root
```python
distance = findDistanceFromRoot(bst , 7)
print(distance)
Output :
3
```
### Binary Search Tree to Doubly Linked List
```python
doubly_linked_list = bstToDLL(bst)
print(doubly_linked_list)
Output :
1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9 -> 10 -> 11 -> 12 -> 13 -> 14 -> 15
```
### Linked List Enumeration
The function `enumerateLinkedList(doubly_linked_list)` is used to enumerate through the linked list . It gives three items in the tuple of list that is (index , node , node_data)
```python
new_bst = createBSTWithHeight(2)
# created new bst with height of 2 .
doubly_linked_list = bstToDLL(new_bst)
for index , node , data in enumerateLinkedList(doubly_linked_list) :
print(f"index : {index} , node : {node} , node data : {data}")
Output :
index : 0 , node : LinkedListNode(data = 1 , prev = . , next = 2) , node data : 1
index : 1 , node : LinkedListNode(data = 2 , prev = 1 , next = 3) , node data : 2
index : 2 , node : LinkedListNode(data = 3 , prev = 2 , next = .) , node data : 3
```
### Serialization and Deserialization Of Binary Search Tree.
The library has `BSTSerializer` class which is used for Binary Tree Serialization and DeSerialization .
There are two functions in the class `serialize()` which returns a string of serialied binary serach tree and `deSerialize()` which returns the root of the deSerialized Binary Search Tree .
```python
serializer = BSTSerializer()
serialized_string = serializer.serialize(bst)
print(f" Serialized BST String : {serialized_string}") # serialized string
deserialized_bst = serializer.deSerialize(serialized_string) # root of the binary tree.
print(f"Deserialized Binary Search Tree ")
print(deserialized_bst)
Output :
Serialized BST String : 8.4.2.1.N.N.3.N.N.6.5.N.N.7.N.N.12.10.9.N.N.11.N.N.14.13.N.N.15.N
Deserialized Binary Search Tree
8
______/ \_____
4 12
__/ \_ __/ \__
2 6 10 14
/ \ / \ / \ / \
1 3 5 7 9 11 13 15
```
There are more functions in the library to work with .
`isBST(root)` : The function checks whether the given tree is BST or not .
`bstSum` : The function gives the sum of all the values of the Binary Search Tree .
`diameterOfBST` : The function gives the biggest path of the tree or the diameter of the tree .
`kThSmallestElement` : The function gives the kth smallest element in the bst .
`kThLargetElement` : The function gives the kth largest element in the bst.
`findMinInBST` : The function gives the smallest node in BST.
`findMaxInBST` : The function gives the largest node in BST.
```python
is_bst = isBST(bst)
print(f"Is Bst : {is_bst}")
bst_sum = bstSum(bst)
print(bst)
print(f"Sum of nodes of the Binary Search Tree : {bst_sum}")
diameter_of_bst = diameterOfBST(bst)
print(f"Diameter of Binary Search Tree: {diameter_of_bst}")
kth_smallest = kThSmallestNode(bst , 6)
print(f"k th smallest node in Binary Search Tree :\n{kth_smallest}")
kth_largest = kThLargestNode(bst , 4)
print(f"k th largest node in Binary Search Tree: \n{kth_largest}")
min_element = findMinInBST(bst)
print(f"Minimum value in BST : \n{min_element}")
max_element = findMaxInBST(bst)
print(f"Maximum value in BST : \n{max_element}")
```
```python
Output :
Is Bst : True
Sum of nodes of the Binary Search Tree : 496
Diameter of Binary Search Tree: 8
k th smallest node in Binary Search Tree :
6
/ \
5 7
k th largest node in Binary Search Tree:
28
__/ \__
26 30
/ \ / \
25 27 29 31
Minimum value in BST :
1
Maximum value in BST :
15
```
Raw data
{
"_id": null,
"home_page": "https://github.com/omkashyap007/Binary-Search-Tree-Library/tree/master",
"name": "bstq",
"maintainer": "",
"docs_url": null,
"requires_python": "",
"maintainer_email": "",
"keywords": "bst,binary search tree,binarytree,binary tree",
"author": "Om Kashyap",
"author_email": "omkashyapcric@gmail.com",
"download_url": "https://files.pythonhosted.org/packages/4b/22/4f7384ac8d64d4c48529f9c48efc472d9990ca75e0cc263de72089ddfc87/bstq-1.0.1.tar.gz",
"platform": null,
"description": "# [BSTq](https://github.com/omkashyap007/Binary-Search-Tree-Library/tree/master)\r\n\r\nBSTq is a comprehensive Python library dedicated to Binary Search Trees (BSTs). Designed to work with BSTs, this library offers a wide array of functions and utilities, rather than basic functions to work with binary search trees effortlessly. \r\n\r\nThis library has lots of functions which can be used to minimize your efforts for Binary Search Trees .\r\n## Install\r\n```\r\npip install bstq\r\n```\r\n\r\n## Usage\r\n```\r\nfrom bstq import *\r\n```\r\n\r\n### Creating Binary Search Tree\r\n\r\nThe following class is used to create a BinarySearchTree and instanciate a tree object with root value of 10 .\r\n```python\r\n\r\nclass BinarySearchTree:\r\n def __init__(self , data , left = None, right = None) :\r\n self.data = data\r\n self.left = left\r\n self.right = right\r\n \r\nroot = BinarySearchTree(10)\r\n```\r\n\r\n### Create Binary Search Tree from Sorted list.\r\nYou have to provide a sorted list which you will paas in the `createBSTFromSortedList` , the function will return a root of the Binary Search Tree created from the list .\r\n\r\n```python\r\n\r\nl = [11, 14, 36, 64, 69, 71, 83, 83] # sorted list.\r\n\r\nroot = createBSTFromSortedList(l)\r\nprint(root)\r\n\r\nOutput :\r\n\r\nSorted List : [11, 14, 36, 64, 69, 71, 83, 83]\r\n 64\r\n __/ \\__ \r\n 14 71 \r\n / \\ / \\ \r\n11 36 69 83 \r\n \\ \r\n 83\r\n\r\n```\r\n### Create Binary Search Tree With given Height .\r\n\r\nYou can use `createBSTWithHeight` function to create BST with given height.\r\n\r\n```\r\nbst = createBSTWithHeight(4)\r\nprint(bst)\r\n```\r\n```\r\nOutput :\r\n 8\r\n ______/ \\_____\r\n 4 12\r\n __/ \\_ __/ \\__\r\n 2 6 10 14\r\n / \\ / \\ / \\ / \\\r\n1 3 5 7 9 11 13 15\r\n\r\n```\r\n\r\n## InOrder , PreOrder , PostOrder , LevelOrder Traversals .\r\nThere are two methods for traversals , one is class based which is specific to class and another is global method for bst.\r\n\r\n```python\r\nin_order = bst.inOrder() # class method\r\nin_order = inOrder(bst) # global method\r\nprint(f\"In Order : {in_order}\")\r\n\r\npre_order = bst.preOrder() # class method\r\npre_order = preOrder(bst) # global method\r\nprint(f\"Pre Order : {pre_order}\")\r\n\r\npost_order = bst.postOrder() # class method\r\npost_order = postOrder(bst) # global method\r\nprint(f\"Post Order : {post_order}\")\r\n\r\nlevel_order = bst.levelOrder() # class method\r\nlevel_order = levelOrder(bst) # global method\r\nprint(f\"Level Order : {level_order}\")\r\n```\r\n\r\n```\r\nOutput :\r\nIn Order : [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15]\r\nPre Order : [8, 4, 2, 1, 3, 6, 5, 7, 12, 10, 9, 11, 14, 13, 15] \r\nPost Order : [1, 3, 2, 5, 7, 6, 4, 9, 11, 10, 13, 15, 14, 12, 8] \r\nLevel Order : [8, 4, 12, 2, 6, 10, 14, 1, 3, 5, 7, 9, 11, 13, 15]\r\n```\r\n\r\n### List Level Order Traversal\r\nThis function gives the list of all the levels of bst .\r\n\r\n```\r\nlevel_order_list = bst.levelOrderList()\r\nlevel_order_list = levelOrderList(bst)\r\nprint(level_order_list)\r\n```\r\n\r\n```\r\nOutput :\r\n[[8], [4, 12], [2, 6, 10, 14], [1, 3, 5, 7, 9, 11, 13, 15]]\r\n```\r\n\r\n### Search in bst\r\n```python\r\nnode = searchInBST(bst , 6)\r\nnode = bst.searchInBST(6)\r\nprint(node)\r\n\r\nOuput :\r\n 6\r\n / \\\r\n5 7\r\n```\r\n\r\n### Height of bst\r\n\r\n```python\r\nh = bst.height()\r\nh = height(bst)\r\n\r\nOutput :\r\n4\r\n```\r\n\r\n### Printing Binary Tree\r\nYou will get the most prettiest display of Binary Search Tree .\r\n```\r\nprintBTree(bst) # global function\r\nprint(bst) # you can also use print function directly .\r\n\r\nOutput :\r\n 8\r\n ______/ \\_____\r\n 4 12\r\n __/ \\_ __/ \\__\r\n 2 6 10 14\r\n / \\ / \\ / \\ / \\\r\n1 3 5 7 9 11 13 15\r\n```\r\n\r\n### Printing the Binary Search Tree Horizontally Flipped .\r\n\r\nYou cannot use the print function , you have to use `printBTree()` with inverted parameter to be True\r\n\r\n```python\r\nprintBTree(bst , inverted = True)\r\n\r\nOutput :\r\n\r\n1 3 5 7 9 11 13 15\r\n \\ / \\ / \\ / \\ / \r\n 2 6 10 14 \r\n \u00c2\u00af\u00c2\u00af\\ /\u00c2\u00af \u00c2\u00af\u00c2\u00af\\ /\u00c2\u00af\u00c2\u00af \r\n 4 12 \r\n \u00c2\u00af\u00c2\u00af\u00c2\u00af\u00c2\u00af\u00c2\u00af\u00c2\u00af\\ /\u00c2\u00af\u00c2\u00af\u00c2\u00af\u00c2\u00af\u00c2\u00af\r\n 8\r\n\r\n```\r\n\r\n### Invert BST\r\nInvertes the binary search tree to its mirror image .\r\n```python\r\ninverted_tree = invertBST(bst)\r\nprint(inverted_tree)\r\n\r\n 8\r\n ______/ \\______\r\n 12 4\r\n __/ \\__ __/ \\_\r\n 14 10 6 2\r\n / \\ / \\ / \\ / \\\r\n15 13 11 9 7 5 3 1\r\n```\r\n### Top View of BST\r\n```python\r\ntop_view = topViewOfBST(bst)\r\nprint(top_view)\r\n\r\nOutput :\r\n[1, 2, 4, 8, 12, 14, 15]\r\n```\r\n### Delete Node in BST\r\nGives and new node with delete bst and also deletes from the actual one.\r\n```python\r\nnew_bst = deleteNodeInBST(bst , 6)\r\nprint(new_bst)\r\n\r\nOutput :\r\n 8\r\n _____/ \\_____\r\n 4 12\r\n / \\ __/ \\__\r\n 2 5 10 14\r\n / \\ \\ / \\ / \\\r\n1 3 7 9 11 13 15\r\n```\r\n\r\n### Distance of Node From Root\r\n```python\r\ndistance = findDistanceFromRoot(bst , 7)\r\nprint(distance)\r\n\r\nOutput :\r\n3\r\n```\r\n\r\n### Binary Search Tree to Doubly Linked List\r\n\r\n```python\r\ndoubly_linked_list = bstToDLL(bst)\r\nprint(doubly_linked_list)\r\n\r\nOutput :\r\n1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9 -> 10 -> 11 -> 12 -> 13 -> 14 -> 15\r\n```\r\n\r\n### Linked List Enumeration\r\nThe function `enumerateLinkedList(doubly_linked_list)` is used to enumerate through the linked list . It gives three items in the tuple of list that is (index , node , node_data)\r\n```python\r\nnew_bst = createBSTWithHeight(2)\r\n# created new bst with height of 2 .\r\ndoubly_linked_list = bstToDLL(new_bst)\r\nfor index , node , data in enumerateLinkedList(doubly_linked_list) :\r\n print(f\"index : {index} , node : {node} , node data : {data}\")\r\n\r\nOutput :\r\nindex : 0 , node : LinkedListNode(data = 1 , prev = . , next = 2) , node data : 1\r\nindex : 1 , node : LinkedListNode(data = 2 , prev = 1 , next = 3) , node data : 2\r\nindex : 2 , node : LinkedListNode(data = 3 , prev = 2 , next = .) , node data : 3\r\n```\r\n### Serialization and Deserialization Of Binary Search Tree.\r\n\r\nThe library has `BSTSerializer` class which is used for Binary Tree Serialization and DeSerialization . \r\n\r\nThere are two functions in the class `serialize()` which returns a string of serialied binary serach tree and `deSerialize()` which returns the root of the deSerialized Binary Search Tree .\r\n```python\r\n\r\nserializer = BSTSerializer()\r\nserialized_string = serializer.serialize(bst)\r\nprint(f\" Serialized BST String : {serialized_string}\") # serialized string\r\ndeserialized_bst = serializer.deSerialize(serialized_string) # root of the binary tree.\r\n\r\nprint(f\"Deserialized Binary Search Tree \")\r\nprint(deserialized_bst)\r\n\r\nOutput :\r\n\r\nSerialized BST String : 8.4.2.1.N.N.3.N.N.6.5.N.N.7.N.N.12.10.9.N.N.11.N.N.14.13.N.N.15.N\r\n\r\nDeserialized Binary Search Tree\r\n 8\r\n ______/ \\_____\r\n 4 12\r\n __/ \\_ __/ \\__\r\n 2 6 10 14\r\n / \\ / \\ / \\ / \\\r\n1 3 5 7 9 11 13 15\r\n```\r\n\r\n\r\nThere are more functions in the library to work with .\r\n\r\n`isBST(root)` : The function checks whether the given tree is BST or not .\r\n`bstSum` : The function gives the sum of all the values of the Binary Search Tree .\r\n`diameterOfBST` : The function gives the biggest path of the tree or the diameter of the tree . \r\n`kThSmallestElement` : The function gives the kth smallest element in the bst .\r\n`kThLargetElement` : The function gives the kth largest element in the bst. \r\n`findMinInBST` : The function gives the smallest node in BST.\r\n`findMaxInBST` : The function gives the largest node in BST.\r\n```python\r\nis_bst = isBST(bst)\r\nprint(f\"Is Bst : {is_bst}\")\r\nbst_sum = bstSum(bst)\r\nprint(bst)\r\nprint(f\"Sum of nodes of the Binary Search Tree : {bst_sum}\")\r\n\r\ndiameter_of_bst = diameterOfBST(bst)\r\nprint(f\"Diameter of Binary Search Tree: {diameter_of_bst}\")\r\n\r\nkth_smallest = kThSmallestNode(bst , 6)\r\nprint(f\"k th smallest node in Binary Search Tree :\\n{kth_smallest}\")\r\n\r\nkth_largest = kThLargestNode(bst , 4)\r\nprint(f\"k th largest node in Binary Search Tree: \\n{kth_largest}\")\r\n\r\nmin_element = findMinInBST(bst)\r\nprint(f\"Minimum value in BST : \\n{min_element}\")\r\n\r\nmax_element = findMaxInBST(bst)\r\nprint(f\"Maximum value in BST : \\n{max_element}\")\r\n```\r\n\r\n```python\r\nOutput :\r\n\r\nIs Bst : True\r\n\r\nSum of nodes of the Binary Search Tree : 496\r\n\r\nDiameter of Binary Search Tree: 8\r\n\r\nk th smallest node in Binary Search Tree :\r\n 6\r\n / \\\r\n5 7\r\n\r\nk th largest node in Binary Search Tree: \r\n 28\r\n __/ \\__\r\n 26 30\r\n / \\ / \\\r\n25 27 29 31\r\n\r\nMinimum value in BST : \r\n1\r\nMaximum value in BST : \r\n15\r\n\r\n```\r\n",
"bugtrack_url": null,
"license": "MIT",
"summary": "Comphrensive Library for Binary Search Trees.",
"version": "1.0.1",
"project_urls": {
"Homepage": "https://github.com/omkashyap007/Binary-Search-Tree-Library/tree/master"
},
"split_keywords": [
"bst",
"binary search tree",
"binarytree",
"binary tree"
],
"urls": [
{
"comment_text": "",
"digests": {
"blake2b_256": "603a5fc166f3c8c931b852113d2a0e25a621c739c034599278b5327059b42646",
"md5": "0a88aba6d458abc39af7a120d97112af",
"sha256": "4d16977b66bdc8574461680a8744012aea4be98908f04ea45ac2cb866839c803"
},
"downloads": -1,
"filename": "bstq-1.0.1-py3-none-any.whl",
"has_sig": false,
"md5_digest": "0a88aba6d458abc39af7a120d97112af",
"packagetype": "bdist_wheel",
"python_version": "py3",
"requires_python": null,
"size": 11252,
"upload_time": "2024-01-10T22:19:36",
"upload_time_iso_8601": "2024-01-10T22:19:36.001171Z",
"url": "https://files.pythonhosted.org/packages/60/3a/5fc166f3c8c931b852113d2a0e25a621c739c034599278b5327059b42646/bstq-1.0.1-py3-none-any.whl",
"yanked": false,
"yanked_reason": null
},
{
"comment_text": "",
"digests": {
"blake2b_256": "4b224f7384ac8d64d4c48529f9c48efc472d9990ca75e0cc263de72089ddfc87",
"md5": "c1cc0ac23176db98f322f17e2e8717de",
"sha256": "58c1bdc795355322883d57a7b2b5b06d9a32af1d33eddd3dd1a350e07076f264"
},
"downloads": -1,
"filename": "bstq-1.0.1.tar.gz",
"has_sig": false,
"md5_digest": "c1cc0ac23176db98f322f17e2e8717de",
"packagetype": "sdist",
"python_version": "source",
"requires_python": null,
"size": 13287,
"upload_time": "2024-01-10T22:19:37",
"upload_time_iso_8601": "2024-01-10T22:19:37.529187Z",
"url": "https://files.pythonhosted.org/packages/4b/22/4f7384ac8d64d4c48529f9c48efc472d9990ca75e0cc263de72089ddfc87/bstq-1.0.1.tar.gz",
"yanked": false,
"yanked_reason": null
}
],
"upload_time": "2024-01-10 22:19:37",
"github": true,
"gitlab": false,
"bitbucket": false,
"codeberg": false,
"github_user": "omkashyap007",
"github_project": "Binary-Search-Tree-Library",
"travis_ci": false,
"coveralls": false,
"github_actions": false,
"lcname": "bstq"
}
JSON
