Analytics Vidhya
Published in

Analytics Vidhya

A brief introduction to Binary Search Tree (BST) using Python

An illustration of inverted tree trunk for better understanding.

It’s called a “tree” because it vaguely resembles an inverted tree trunk with branches.

  • The word “binary” indicates that each “node” in the tree can have at most 2 children (left or right).
  • Nodes can have 0, 1 or 2 children. Nodes that do not have any children are sometimes also called “leaves”.
  • The single node at the top is called the “root” node, and it typically where operations like search, insertion etc. begin.

A Binary Tree

To begin, we’ll create simple binary tree(without any of the additional properties) containing numbers as keys within nodes. Here’s an example:

#simple class representing a node within a binary tree.class TreeNode:
def __init__(self, key):
self.key = key
self.left = None
self.right = None
#create objects representing each node of the above treenode0 = TreeNode(3)
node1 = TreeNode(4)
node2 = TreeNode(5)
#connect the nodes by setting the .left and .right properties of the root node. And we're done! We can create a new variable tree which simply points to the root node, and use it to access all the nodes within the tree.node0.left = node1
node0.right = node2
#Going forward, we'll use the term "tree" to refer to the root node. The term "node" can refer to any node in a tree, not necessarily the root.

A traversal refers to the process of visiting each node of a tree exactly once. Visiting a node generally refers to adding the node’s key to a list. There are three ways to traverse a binary tree and return the list of visited keys:

Inorder traversal

  1. Traverse the left subtree recursively inorder.
  2. Traverse the current node.
  3. Traverse the right subtree recursively inorder.

Preorder traversal

  1. Traverse the current node.
  2. Traverse the left subtree recursively preorder.
  3. Traverse the right subtree recursively preorder.

Postorder traversal

  1. Traverse the left subtree recursively postorder.
  2. Traverse the right subtree recursively postorder.
  3. Traverse the current node.
#implementation of inorder traversal of a binary treedef traverse_in_order(node):
if node is None:
return []
return(traverse_in_order(node.left) +
[node.key] +
traverse_in_order(node.right))

The height/depth of a binary tree is defined as the length of the longest path from its root node to a leaf.

#computation of height/depth of a binary treedef tree_height(node):
if node is None:
return 0
return 1 + max(tree_height(node.left), tree_height(node.right))
# computation of number of nodes in a binary treedef tree_size(node):
if node is None:
return 0
return 1 + tree_size(node.left) + tree_size(node.right)

A Binary Search Tree (BST)

A binary search tree or BST is a binary tree that satisfies the following conditions:

  1. The left subtree of any node only contains nodes with keys less than the node’s key
  2. The right subtree of any node only contains nodes with keys greater than the node’s key
#Function to check if a binary tree is a binary search tree and to find the minimum and maximum key in a binary treedef is_bst(node):
if node is None:
return True, None, None

is_bst_l, min_l, max_l = is_bst(node.left)
is_bst_r, min_r, max_r = is_bst(node.right)

is_bst_node = (is_bst_l and is_bst_r and
(max_l is None or node.key > max_l) and
(min_r is None or node.key < min_r))

min_key = min(remove_none([min_l, node.key, min_r]))
max_key = max(remove_none([max_l, node.key, max_r]))

print(node.key, min_key, max_key, is_bst_node)

return is_bst_node, min_key, max_key

Using the BST-property to perform insertion efficiently:

  1. Starting from the root node, compare the key to be inserted with the current node’s key
  2. If the key is smaller, recursively insert it in the left subtree (if it exists) or attach it as as the left child if no left subtree exists.
  3. If the key is larger, recursively insert it in the right subtree (if it exists) or attach it as as the right child if no right subtree exists.
#Implementation of insertiondef insert(node, key, value):
if node is None:
node = BSTNode(key, value)
elif key < node.key:
node.left = insert(node.left, key, value)
node.left.parent = node
elif key > node.key:
node.right = insert(node.right, key, value)
node.right.parent = node
return node
#Implementation of finding a nodedef find(node, key):
if node is None:
return None
if key == node.key:
return node
if key < node.key:
return find(node.left, key)
if key > node.key:
return find(node.right, key)
#Implementation of updatedef update(node, key, value):
target = find(node, key)
if target is not None:
target.value = value
def list_all(node):
if node is None:
return []
return list_all(node.left) + [(node.key, node.value)] + list_all(node.right)

Applications of Binary Search Trees (BSTs)

BSTs are used for a lot of applications due to its ordered structure.

  • BSTs are used for indexing and multi-level indexing.
  • They are also helpful to implement various searching algorithms.
  • It is helpful in maintaining a sorted stream of data.
  • TreeMap and TreeSet data structures are internally implemented using self-balancing BSTs.

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store