Binary Search Tree Python

Last Updated On Tuesday 5th Oct 2021

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