Loading lesson path
Concept visual
A Binary Search Tree is a Binary Tree where every node's left child has a lower value, and every node's right child has a higher value. A clear advantage with Binary Search Trees is that operations like search, delete, and insert are fast and done without having to shift values in memory.
A Binary Search Tree (BST) is a type of Binary Tree data structure, where the following properties must be true for any node "X" in the tree: The X node's left child and all of its descendants (children, children's children, and so on) have lower values than X's value. The right child, and all its descendants have higher values than X's value. Left and right subtrees must also be Binary Search Trees. These properties makes it faster to search, add and delete values than a regular binary tree.
To make this as easy to understand and implement as possible, let's also assume that all values in a Binary Search Tree are unique.Use the Binary Search Tree below to better understand these concepts and relevant terminology. Binary Search Tree (BST)
Formula
Tree size (n = 8)7's left child 7's right child
Formula
Tree height (h = 3)
15's height (h = 2)13's right subtree
Formula
13's in - order successor13
15
14 19 18 The size of a tree is the number of nodes in it (\(n\)). A subtree starts with one of the nodes in the tree as a local root, and consists of that node and all its descendants. The descendants of a node are all the child nodes of that node, and all their child nodes, and so on. Just start with a node, and the descendants will be all nodes that are connected below that node. The node's height is the maximum number of edges between that node and a leaf node. A node's in-order successor is the node that comes after it if we were to do in-order traversal. In-order traversal of the BST above would result in node 13 coming before node 14, and so the successor of node 13 is node 14.
Just to confirm that we actually have a Binary Search Tree data structure in front of us, we can check if the properties at the top of this page are true. So for every node in the figure above, check if all the values to the left of the node are lower, and that all values to the right are higher. Another way to check if a Binary Tree is BST, is to do an in-order traversal (like we did on the previous page) and check if the resulting list of values are in an increasing order. The code below is an implementation of the Binary Search Tree in the figure above, with traversal.
class TreeNode:
def __init__(self, data):Formula
self.data = data self.left = None self.right = Nonedef inOrderTraversal(node):if node is None:
return inOrderTraversal(node.left)
print(node.data, end=", ")
inOrderTraversal(node.right)Formula
root = TreeNode(13)
node7 = TreeNode(7)
node15 = TreeNode(15)
node3 = TreeNode(3)
node8 = TreeNode(8)
node14 = TreeNode(14)
node19 = TreeNode(19)
node18 = TreeNode(18)Formula
root.left = node7 root.right = node15Formula
node7.left = node3 node7.right = node8Formula
node15.left = node14 node15.right = node19Formula
node19.left = node18# Traverse inOrderTraversal(root) As we can see by running the code example above, the in-order traversal produces a list of numbers in an increasing (ascending) order, which means that this Binary Tree is a Binary Search Tree.
Searching for a value in a BST is very similar to how we found a value using Binary Search on an array. For Binary Search to work, the array must be sorted already, and searching for a value in an array can then be done really fast. Similarly, searching for a value in a BST can also be done really fast because of how the nodes are placed.
Start at the root node.
If this is the value we are looking for, return.If the value we are looking for is higher, continue searching in the right subtree. If the value we are looking for is lower, continue searching in the left subtree. If the subtree we want to search does not exist, depending on the programming language, return None, or NULL, or something similar, to indicate that the value is not inside the BST. Use the animation below to see how we search for a value in a Binary Search Tree. Click Search. 13
15
14 19 18
18 51
The algorithm above can be implemented like this:
def search(node, target):if node is None:
return None elif node.data == target:
return node elif target < node.data:
return search(node.left, target)
else:
return search(node.right, target)
The time complexity for searching a BST for a value is \(O(h)\), where \(h\) is the height of the tree.For a BST with most nodes on the right side for example, the height of the tree becomes larger than it needs to be, and the worst case search will take longer. Such trees are called unbalanced. 13
15
14 19 18
13
15
19 14 18
Both Binary Search Trees above have the same nodes, and in-order traversal of both trees gives us the same result but the height is very different. It takes longer time to search the unbalanced tree above because it is higher. We will use the next page to describe a type of Binary Tree called AVL Trees. AVL trees are self-balancing, which means that the height of the tree is kept to a minimum so that operations like search, insertion and deletion take less time.
Inserting a node in a BST is similar to searching for a value.
Start at the root node.
Is the value lower? Go left. Is the value higher? Go right. Continue to compare nodes with the new value until there is no right or left to compare with. That is where the new node is inserted. Inserting nodes as described above means that an inserted node will always become a new leaf node. Use the simulation below to see how new nodes are inserted. Click Insert. 13
15
14 19 18 10 10 17 51
All nodes in the BST are unique, so in case we find the same value as the one we want to insert, we do nothing. This is how node insertion in BST can be implemented:
def insert(node, data):if node is None:
return TreeNode(data)
else:if data < node.data:
Formula
node.left = insert(node.left, data)elif data > node.data:Formula
node.right = insert(node.right, data)return nodeFind The Lowest Value in a BST Subtree The next section will explain how we can delete a node in a BST, but to do that we need a function that finds the lowest value in a node's subtree.
Start at the root node of the subtree. Go left as far as possible. The node you end up in is the node with the lowest value in that BST subtree. In the figure below, if we start at node 13 and keep going left, we end up in node 3, which is the lowest value, right? And if we start at node 15 and keep going left, we end up in node 14, which is the lowest value in node 15's subtree. 13
15
14 19 18 13 15
This is how the function for finding the lowest value in the subtree of a BST node looks like: