BinarySearchTrees
Initialize a BST
BST can be initialized in two ways
- First by a list, which makes a balanced binary search tree
- By constructing a tree from scratch.
From list
from structlinks.DataStructures import BinarySearchTree bst = BinarySearchTree.create_tree([1, 2, 4, 10, 20, 30, 3]) print(bst) # Output: # _4___ # / \ # 2 20_ # / \ / \ # 1 3 10 30
Properties
from structlinks.DataStructures import BinarySearchTree bst = BinarySearchTree.create_tree([1, 2, 4, 10, 20]) print(bst) # Output: # 4___ # / \ # 2 20 # / / # 1 10 print(bst.root) # root value # Output: # 4 print(bst.left) # copy of left child # Output: # 2 # / # 1 print(bst.right) # copy of right child # Output: # 20 # / # 10 print(bst.height) # height of the tree # Output: # 3 print(bst.is_balanced) # Weather tree is balanced # Output: # True
Item in BST
from structlinks.DataStructures import BinarySearchTree bst = BinarySearchTree.create_tree([2, 1, 3, 3, 5, 4]) print(3 in bst) # Output: # True print(100 in bst) # Output: # False
Insert Item in BST
from structlinks.DataStructures import BinarySearchTree bst = BinarySearchTree.create_tree([1, 2, 4, 10, 20]) print(bst) # Output: # 4___ # / \ # 2 20 # / / # 1 10 bst.insert(3) print(bst) # Output: # _4___ # / \ # 2 20 # / \ / # 1 3 10
Remove Item from BST
from structlinks.DataStructures import BinarySearchTree bst = BinarySearchTree.create_tree([1, 2, 3, 4, 5]) print(bst) # Output: # 3_ # / \ # 2 5 # / / # 1 4 bst.remove(2) print(bst) # Output: # 3_ # / \ # 1 5 # / # 4
Convert to List
from structlinks.DataStructures import BinarySearchTree bst = BinarySearchTree.create_tree([2, 1, 3, 5, 4]) print(bst.to_list()) # Output: # [1, 2, 3, 4, 5]
Invert the BST
from structlinks.DataStructures import BinarySearchTree bst = BinarySearchTree.create_tree([1, 2, 3, 4, 5]) print(bst) # Output: # 3_ # / \ # 2 5 # / / # 1 4 bst.invert() print(bst) # Output: # _3 # / \ # 5 2 # \ \ # 4 1