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

## Why is it called a tree?

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.classTreeNode:

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)#connectthe nodes by setting the .left and .right properties of the root node. And we're done! We can create a new variabletreewhich 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.

## Traversing a Binary Tree

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*

- Traverse the left subtree recursively inorder.
- Traverse the current node.
- Traverse the right subtree recursively inorder.

*Preorder traversal*

- Traverse the current node.
- Traverse the left subtree recursively preorder.
- Traverse the right subtree recursively preorder.

*Postorder traversal*

- Traverse the left subtree recursively postorder.
- Traverse the right subtree recursively postorder.
- Traverse the current node.

#implementation of inorder traversal of a binary treedeftraverse_in_order(node):

if node is None:

return []

return(traverse_in_order(node.left) +

[node.key] +

traverse_in_order(node.right))

## Height and Size of Binary Tree

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 treedeftree_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 treedeftree_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:

- The left subtree of any node only contains nodes with keys less than the node’s key
- 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 treedefis_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

## Insertion in BST

Using the BST-property to perform insertion efficiently:

- Starting from the root node, compare the key to be inserted with the current node’s key
- 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.
- 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 insertiondefinsert(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

## Finding a particular node in BST

#Implementation of finding a nodedeffind(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)

## Updating value in BST

#Implementation of updatedefupdate(node, key, value):

target = find(node, key)

if target is not None:

target.value = value

## Retrieving all the key-value pairs stored in BST in sorted order of keys

`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.