Docs Binary Search Tree (BST) on GitHub

Binary Search Tree (BST)¶

A binary search tree, or BST for short, is a non-linear data structure that stores numbers hierarchical. With the exception of the top element, each element in the binary serach tree has a parent element and each node has two children elements at most. We typically call the top element of the binary search tree, “the root”. The root is drawn as the highest element, with the other elements being connected below (just the opposite of an actual tree).

In other words, we can consider the binary search tree as a binary tree that stores numbers where the value stored in a certain node is greater than all the numbers found in the node’s left subtree and less than those found in the node’s right subtree.

So, the following is a simple BST:

      __8___
     /      \
  __5       _15
 /   \    /
2     7   10
 \
  3

In the previous binary search tree, we can say the following:

8 has no parent.
8 is the parent of both 5 and 15. 5 is the left child of 8 and 15 is the right child.
8 is the grandparnet of 2, 7 and 10.
15 is the uncle of 2 and 7. While 5 is the uncle of just 10.
15 is the sibling of 5 and vice versa. And 2 is the sibling of 7 and vice versa.

Now, let’s try to use the previous BST to explain a few terms:

Tree Node: Each entry in the BSTis called a tree node. So, 8, 5, 15, … 3 are all tree nodes. So, the number of nodes in the previous BST is 7.
Root: The root is the first tree node in the BST and it’s the only tree node that has no parent. So, 8 is the root of the previuos tree.
Leaf Node: The leaf node is a tree node that has no children. So, both 3, 7, and 10 are leaf nodes. So, the number of leaf nodes in the previous tree is 3.
Height: The tree height is the number of edges between the root and the furthest leaf node. In this case, the tree height is just 3 as there are three edges between 8 and 3.
Depth: The depth of a tree node is the number of edges between this tree node and the root. So, the depth of the tree’s root is always 0.
Balanced Tree: A BST is said to be balanced if the difference between the depth of any two leaf nodes is less than or equal one. So, this BST is balanced
Perfect Tree: A BST is said to be perfect if all its levels are completely filled. So, the pervious BST is NOT perfect.
Strict Tree: A BST is said to be strict if all its non-leaf nodes has left and right children. So, the pervious BST is NOT strict.
Traversal: Traversal is the process to visit all nodes of a BST starting from the root as we cannot randomly access any node in a BST. There are four ways which we use to traverse a BST:
- Pre-order Traversal: It’s also known as “Depth-first Traversal” where the parent is visited first. Then, the left subtree (if found), then the right subtree (if found). So, the pre-order traversal of the previous BST will be:
  
  8 ⟶ 5 ⟶ 2 ⟶ 3 ⟶ 7 ⟶ 15 ⟶ 10
- In-order Traversal: The left subtree (if found) is visited first . Then, the parent then the right subtree (if found). So, the in-order traversal of the previous BST will be:
  
  2 ⟶ 3 ⟶ 5 ⟶ 7 ⟶ 8 ⟶ 10 ⟶ 15
- Post-order Traversal: The left subtree (if found) is visited first. Then, the right subtree (if found) then the parent. So, the post-order traversal of the previous BST will be:
  
  3 ⟶ 2 ⟶ 7 ⟶ 5 ⟶ 10 ⟶ 15 ⟶ 8
- Breadth-order Traversal: It’s also known as “Level-order Traversal” where all nodes is visited by the order of the level they are in. So, tree nodes in the first level are visited before all tree nodes in the second level and so on. So, the breadth-first traversal of the previuos BST will be:
  
  8 ⟶ 5 ⟶ 15 ⟶ 2 ⟶ 7 ⟶ 10 ⟶ 3

⏱ Time-Complexity¶

The following table sums up all the different public functionality in this class and also provides the worst-case time complexity along side with the optimal time complexity that I will try to reach in future releases Insha’Allah. Generally, we are going to use the following indicators in the table:

n is the number of nodes currently in the BST.
h is the BST height which is log(n) when the tree is balanced.

Method	Description	Worst-case	Optimal
is_empty()	Checks if the BST is empty.	O(1)	O(1)
__len__()	Returns the number of nodes inside the BST.	O(1)	O(1)
__repr__()	Represents the BST.	O(n)	O(n)
__iter__()	Iterates over the BST.	O(n)	O(n)
__contains__()	Checks the existence of the given item.	O(h)	O(h)
get_height()	Gets the BST’s height.	O(n)	O(1)
get_depth()	Gets the BST’s depth.	O(n)	O(1)
get_nodes_per_level()	Returns a list of all nodes per level.	O(n)	O(n)
is_balanced()	Checks if the BST is balanced.	O(n)	O(1)
is_perfect()	Checks if the BST is perfect.	O(n)	O(1)
is_strict()	Checks if the BST is strict.	O(n)	O(1)
count_leaf_nodes()	Counts all leaf nodes in the BST.	O(n)	O(n)
clear()	Clears the whole BST instance.	O(1)	O(1)
to_list()	Converts the BST instance to a normal list.	O(n)	O(n)
traverse()	Traverses the BST based on given method.	O(n)	O(n)
preorder_traverse()	Traverses the BST in an pre-order manner.	O(n)	O(n)
inorder_traverse()	Traverses the BST in an in-order manner.	O(n)	O(n)
postorder_traverse()	Traverses the BST in an post-order manner.	O(n)	O(n)
breadth_first_traverse()	Traverses the BST level by level.	O(n)	O(n)
depth_first_traverse()	Traverses the BST in an pre-order manner.	O(n)	O(n)
get_min()	Gets the minimum number in the BST.	O(h)	O(h)
get_max()	Gets the maximum number in the BST.	O(h)	O(h)
insert()	Inserts a certain value to the BST.	O(h)	O(h)
remove()	Removes a certain value from the BST.	O(h)	O(h)

☕️ API¶

Here are all of the public methods that can be used with BST() objects:

class extra.trees.bst.BST(iterable=None)¶

A BST is a non-linear data structure that can be defined recursively using a collection of binary tree nodes, where each node contains a numeric value and it has either zero, one or two references to the children binary tree nodes. And the value holding by the node must be greater than all values being hold by the left subtree and smaller that all the values being hold by the right subtree.

__contains__(find_val)¶

Searches the BST() for the given value and returns True if the value exists and False if not.

Parameters:	find_val (int or float) – The value to be searched for in the BST() instance.
Returns:	Returns True if the value exists in the BST() instance and False if not.
Return type:	bool

Example

>>> bst = BST([8, 5, 2, 7, 15, 10, 3])
>>> bst
      __8___
     /      \
  __5       _15
 /   \    /
2     7   10
 \
  3
>>> 5 in bst
True
>> 50 in bst
False

__init__(iterable=None)¶

Initializes a BST() instance using an optiona iterable object in time-complexity of O(n) where n is the number of elements inside the given iterable.

Parameters:	iterable (iterable (default: None)) – An iterable python object that implements the __iter__ method. For example, list and tuple are both iterables.
Raises:	TypeError: – It can be raised in three cases In case the given object isn’t iterable. If one of the elements in the iterable is an Extra object. If one of the elements in the iterable is NOT a number. ValueError: – If one of the iterable elements is None.

Examples

>>> bst = BST([8, 5, 2, 7, 15, 10, 3])
>>> bst
      __8___
     /      \
  __5       _15
 /   \    /
2     7   10
 \
  3

Using an iterable object with None as one of its elements will raise ValueError

>>> BST([2, None])
ValueError: Can't use `None` as an element within `extra.BST()`!!

Using a non-iterable object will raise TypeError

>>> BST(2)
TypeError: The given object isn't iterable!!

Using nested BST() objects will raise TypeError as well

>>> bst_1 = BST([1])
>>> bst_2 = BST([1, bst_1])
TypeError: Can't create `extra.BST()` using `extra.BST()`!!

__iter__()¶

Iterates over the BST() instance and returns a generator of the BSTNode() values in breadth-first manner.

Yields:	int of float – The number stored at each node in the instance.

Example

>>> bst = BST([8, 5, 2, 7, 15, 10, 3])
>>> bst
      __8___
     /      \
  __5       _15
 /   \    /
2     7   10
 \
  3
>>> for value in bst:
...     print(value, end=',')
8,5,15,2,7,10,3,

__len__()¶

Gets the length of the BST() instance in constant time.

Returns:	The length of the BST() instance. Length is the number of tree nodes in the instance.
Return type:	int

Example

>>> bst = BST([2, 1, 3])
>>> bst
    __2__
   /     \
  1       3
>>> len(bst)
3

breadth_first_traverse()¶

Traverses the BST() instance in breadth-first manner. Which means that the tree nodes will be visited level by level.

Returns:	A list of all values of the pre-order visited nodes.
Return type:	list

Example

>>> bst = BST([8, 5, 2, 7, 15, 10, 3])
>>> bst
      __8___
     /      \
  __5       _15
 /   \    /
2     7   10
 \
  3
>>> bst.breadth_first_traverse()
[8, 5, 15, 2, 7, 10, 3]

clear()¶

Removes all nodes within the BST() instance in constant time.

Example

>>> bst = BST([8, 5, 2, 7, 15, 10, 3])
>>> bst
      __8___
     /      \
  __5       _15
 /   \    /
2     7   10
 \
  3
>>> bst.clear()
>>> bst
/ \
>>> bst.is_empty()
True

count_leaf_nodes()¶

Counts the number of leaf nodes in the BST() instance. Leaf nodes are the tree nodes that have no children.

Returns:	A positive integer representing the number of leaf nodes in the BST().
Return type:	int

Example

>>> bst = BST([8, 5, 2, 7, 15, 10, 3])
>>> bst
      __8___
     /      \
  __5       _15
 /   \    /
2     7   10
 \
  3
>>> bst.count_leaf_nodes()
3

depth_first_traverse()¶

Traverses the BST() instance in depth-first manner. Which means that the parent is visited first. Then, the left subtree (if found), then the right subtree (if found).

Note

It’s the same as preorder_traverse() method.

Returns:	A list of all values of the pre-order visited nodes.
Return type:	list

Example

>>> bst = BST([8, 5, 2, 7, 15, 10, 3])
>>> bst
      __8___
     /      \
  __5       _15
 /   \    /
2     7   10
 \
  3
>>> bst.depth_first_traverse()
[8, 5, 2, 3, 7, 15, 10]

get_depth()¶

Gets the depth of the BST() instance.

Returns:	A positive integer representing the depth of the instance.
Return type:	int

Example

>>> bst = BST([8, 5, 2, 7, 15, 10, 3])
>>> bst
      __8___
     /      \
  __5       _15
 /   \    /
2     7   10
 \
  3
>>> bst.get_depth()
0

get_height()¶

Gets the height of the BST() instance. The BST’s height is the number of edges between the root and the furthest leaf node.

Returns:	A positive integer representing the height of the instance.
Return type:	int

Example

>>> bst = BST([8, 5, 2, 7, 15, 10, 3])
>>> bst
      __8___
     /      \
  __5       _15
 /   \    /
2     7   10
 \
  3
>>> bst.get_height()
3

get_max()¶

Gets the maximum value in the BST() isntance. The maximum value can be found at the right-most tree node in the BST() instance.

Returns:	The maximum numeric value in the BST() instance.
Return type:	int or float
Raises:	IndexError: – In case the BST() instance is empty.

Example

>>> bst = BST([8, 5, 2, 7, 15, 10, 3])
>>> bst
      __8___
     /      \
  __5       _15
 /   \    /
2     7   10
 \
  3
>>> bst.get_max()
15

get_min()¶

Gets the minimum value in the BST() isntance. The minimum value can be found at the left-most tree node in the BST() instance.

Returns:	The minimum numeric value in the BST() instance.
Return type:	int or float
Raises:	IndexError: – In case the BST() instance is empty.

Example

>>> bst = BST([8, 5, 2, 7, 15, 10, 3])
>>> bst
      __8___
     /      \
  __5       _15
 /   \    /
2     7   10
 \
  3
>>> bst.get_min()
2

get_nodes_per_level()¶

Retrieves all tree nodes within the BST() instance so that all tree nodes in a certain level will be concatenated into a separate list.

Returns:	A nested list where the first inner-list has all the tree nodes in the first level, the second inner-list has all the tree nodes in the second level, … so on.
Return type:	list

Example

>>> bst = BST([8, 5, 2, 7, 15, 10, 3])
>>> bst
      __8___
     /      \
  __5       _15
 /   \    /
2     7   10
 \
  3
>>> bst.get_nodes_per_level()
[[8], [5, 15], [2, 7, 10], [3]]

inorder_traverse()¶

Traverses the BST() instance in in-order manner. Which means that the left subtree (if found) is visited first. Then, the parent then the right subtree (if found).

Returns:	A list of all values of the in-order visited nodes.
Return type:	list

Example

>>> bst = BST([8, 5, 2, 7, 15, 10, 3])
>>> bst
      __8___
     /      \
  __5       _15
 /   \    /
2     7   10
 \
  3
>>> bst.inrder_traverse()
[2, 3, 5, 7, 8, 10, 15]

insert(value)¶

Inserts a numeric value in the BST() instance according to the rules of binary search trees.

Parameters:	value (int or float) – The new numeric value that will be inserted.
Raises:	ValueError: – If the given value is None. TypeError: – If the given value is not a numeric value.

Example

>>> bst = BST()
>>> bst.insert(10)
>>> bst.insert(5)
>>> bst.insert(15)
>>> bst
  10
 /  \
5    15
>>> bst.insert("2")
TypeError: `extra.BST()` accepts only numbers!!

is_balanced()¶

Checks if the BST() instance is balanced. A BST is balanced if the difference between the depth of any two leaf nodes is less than or equal to one.

Returns:	True if the BST() instance is balanced and False if it is not balanced.
Return type:	bool
Raises:	UserWarning: – If the BST() is empty.

Example

>>> bst = BST([8, 5, 2, 7, 15, 10, 3])
>>> bst
      __8___
     /      \
  __5       _15
 /   \    /
2     7   10
 \
  3
>>> bst.is_balanced()
True

is_empty()¶

Checks if the BST() instance is empty or not in constant time.

Returns:	A boolean flag showing if the BST() instance is empty or not. True shows that this instance is empty and False shows it’s not empty.
Return type:	bool

Example

>>> bst = BST()
>>> bst.is_empty()
True
>>> bst.insert(10)
>>> bst.is_empty()
False

is_perfect()¶

Checks if the BST() instance is perfect. A BST is perfect if all its levels are completely filled.

Returns:	True if the BST() instance is perfect and False if it is not perfect.
Return type:	bool
Raises:	UserWarning: – If the BST() is empty.

Example

>>> bst = BST([8, 5, 2, 7, 15, 10, 3])
>>> bst
      __8___
     /      \
  __5       _15
 /   \    /
2     7   10
 \
  3
>>> bst.is_perfect()
False
>>> bst = BST([8, 5, 2, 7, 15, 10, 20])
>>> bst
      __8___
     /      \
  __5       _15
 /   \    /   \
2     7   10    20
>>> bst.is_perfect()
True

is_strict()¶

Checks if the BST() instance is strict. A BST is strict if all its non-leaf nodes have two children (left and right).

Returns:	True if the BST() instance is strict and False if it is not strict.
Return type:	bool
Raises:	UserWarning: – If the BST() is empty.

Example

>>> bst = BST([8, 5, 2, 7, 15, 10, 3])
>>> bst
      __8___
     /      \
  __5       _15
 /   \    /
2     7   10
 \
  3
>>> bst.is_strict()
False

postorder_traverse()¶

Traverses the BST() instance in post-order manner. Which means that the left subtree (if found) is visited first. Then, the right subtree (if found) then the parent.

Returns:	A list of all values of the pre-order visited nodes.
Return type:	list

Example

>>> bst = BST([8, 5, 2, 7, 15, 10, 3])
>>> bst
      __8___
     /      \
  __5       _15
 /   \    /
2     7   10
 \
  3
>>> bst.postorder_traverse()
[3, 2, 7, 5, 10, 15, 8]

preorder_traverse()¶

Traverses the BST() instance in pre-order manner. Which means that the parent is visited first. Then, the left subtree (if found), then the right subtree (if found).

Note

It’s the same as depth_first_traverse() method.

Returns:	A list of all values of the pre-order visited nodes.
Return type:	list

Example

>>> bst = BST([8, 5, 2, 7, 15, 10, 3])
>>> bst
      __8___
     /      \
  __5       _15
 /   \    /
2     7   10
 \
  3
>>> bst.preorder_traverse()
[8, 5, 2, 3, 7, 15, 10]

remove(del_value)¶

Removes the del_value from the BST() instance.

Parameters:	del_value (int or float) – The value to be deleted from the subtree.
Raises:	UserWarning: – If the BST() instance is empty of if the value wasn’t found in the instance.

Example

>>> bst = BST([8, 5, 2, 7, 15, 10, 3])
>>> bst
      __8___
     /      \
  __5       _15
 /   \    /
2     7   10
 \
  3
>>> bst.remove(5)
>>> bst
      8___
     /    \
  __7     _15
 /       /
2       10
 \
  3
>>> bst.remove(50)
UserWarning: Couldn't find `50` in `extra.BST()`!!

to_list()¶

Converts the BST() instance to a list where values will be inserted in breadth-first manner.

Returns:	A list object containing the same elements as the BST() instance.
Return type:	list

Example

>>> bst = BST([8, 5, 2, 7, 15, 10, 3])
>>> bst
      __8___
     /      \
  __5       _15
 /   \    /
2     7   10
 \
  3
>>> bst.to_list()
[8, 5, 15, 2, 7, 10, 3]

traverse(method='inorder')¶

Traversal is the process to visit all nodes of a BST starting from the root as we cannot randomly access any node in a binary tree. There are four ways which we use to traverse a BST:

preorder - depth-first
inorder
posteorder
breadth-first

Parameters:	method (str (default="inorder")) – A lower-cased string describing the type of traversal that will be used. It could be one of these values: [“inorder”, “postorder”, “preorder”, “depth-first”, “breadth-first”]
Returns:	A list of all values of the visited nodes according to the specified traversal method.
Return type:	list
Raises:	ValueError: – If the given method isn’t known. TypeError: – If the given method isn’t a string.

Example

>>> bst = BST([8, 5, 2, 7, 15, 10, 3])
>>> bst
      __8___
     /      \
  __5       _15
 /   \    /
2     7   10
 \
  3
>>> bst.traverse("preorder")
[8, 5, 2, 3, 7, 15, 10]
>>> bst.traverse("inorder")
[2, 3, 5, 7, 8, 10, 15]
>>> bst.traverse("postorder")
[3, 2, 7, 5, 10, 15, 8]
>>> bst.traverse("breadth-first")
[8, 5, 15, 2, 7, 10, 3]
>>> bst.traverse("extra")
ValueError: Given traverse method has to be one of these:
{'breadth-first', 'postorder', 'inorder', 'depth-first', 'preorder'}

Previous Next

2020, anwarvic

Created using Sphinx (1.8.6) with Minoo (Beta 0.9.7) theme.