DSA Binary Search Trees
A Binary Search Tree is a Binary Tree in which the left child of each node has a lower value and the right child of each node has a greater value.
The fact that Binary Search Trees perform quick operations (such as search, remove, and insert) without requiring the shifting of memory data is a clear benefit.
Binary Search Trees
One sort of Binary Tree data structure is a Binary Search Tree (BST), where each node “X” in the tree must have the following properties:
- The value of the left child of the X node and all of its offspring (children, children’s children, and so on) are less than the value of X.
- The values of the right child and all of its offspring are greater than those of X.
- Binary Search Trees are also required for the left and right subtrees.
Compared to a typical binary tree, these qualities allow for faster searching, adding, and deleting of values.
In order to simplify the explanation and use of this, let us additionally assume that every value within a Binary Search Tree is unique.
To learn more about these ideas and related terms, use the Binary Search Tree below.
==== example mukavu ====
A tree’s number of nodes (n) determines its size.
One of the tree’s nodes serves as the local root of a subtree, which is made up of that node and all of its offspring.
A node’s descendants are all of its offspring nodes, as well as all of their offspring nodes, and so on. Simply begin with a node, and all nodes connected below it will be the descendants.
The maximum number of edges between a node and a leaf node determines the node’s height.
The node that follows a node in an in-order traversal is called its in-order successor. Node 13 would come before Node 14 in the above BST’s in-order traversal, making Node 14 Node 13’s successor.
Traversal of a Binary Search Tree
We may verify that the properties listed at the beginning of this page are true just to make sure we are looking at a Binary Search Tree data structure. Thus, for each node in the accompanying picture, confirm that all values are higher to the right of the node and lower to the left of the node.
Doing an in-order traversal, as we did on the previous page, and determining whether the list of values that results is in increasing order is another method to determine whether a Binary Tree is BST.
An implementation of the Binary Search Tree with traversal is shown in the code below.
Example
Python:
class TreeNode:
def __init__(self, data):
self.data = data
self.left = None
self.right = None
def inOrderTraversal(node):
if node is None:
return
inOrderTraversal(node.left)
print(node.data, end=", ")
inOrderTraversal(node.right)
root = TreeNode(13)
node7 = TreeNode(7)
node15 = TreeNode(15)
node3 = TreeNode(3)
node8 = TreeNode(8)
node14 = TreeNode(14)
node19 = TreeNode(19)
node18 = TreeNode(18)
root.left = node7
root.right = node15
node7.left = node3
node7.right = node8
node15.left = node14
node15.right = node19
node19.left = node18
# Traverse
inOrderTraversal(root)
This Binary Tree is a Binary Search Tree as, as the code example above illustrates, the in-order traverse yields a list of numbers in an increasing (ascending) order.
Search for a Value in a BST
Finding a value using Binary Search on an array is remarkably similar to searching for a value in a BST.
In order for Binary Search to function, the array needs to be sorted first. Once sorted, searching across an array quickly can be done.
In a similar vein, the arrangement of the nodes makes it possible to search for a value in a BST very quickly.
How it works:
- Assume root node first.
- Return if this is the value we are searching for.
- If the desired value is greater, carry on your search within the appropriate subtree.
- Proceed with the left subtree search if the desired value is less.
- Depending on the programming language, return None, NULL, or a similar message to indicate that the value is not inside the BST if the subtree we need to search does not exist.
To show how we look for a value in a Binary Search Tree, use the animation below.
==== example mukavu ====
This is one way to implement the aforementioned algorithm:
Example
Python:
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.
When a BST has the majority of its nodes on the right side, for instance, the tree’s height grows above what is necessary, and the worst-case search will take longer. We refer to these trees as imbalanced.
The nodes in the two above Binary Search Trees are identical, and an in-order traverse of both trees yields the same result, however the heights differ significantly. Because the unbalanced tree above is higher, searching it takes longer.
We shall discuss AVL Trees, a particular kind of Binary Tree, on the following page. Since AVL trees are self-balancing, searches, insertions, and deletions occur more quickly since the tree’s height is minimized.
Insert a Node in a BST
It is analogous to looking for a value to insert a node in a BST.
How it works:
1.Start at the root node.
2.Compare each node:
- Is the value lower? Go left.
- Is the value higher? Go right.
3.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.
When nodes are introduced in the manner mentioned above, they will always develop into new leaf nodes.
View the insertion of new nodes by using the simulation below.
==== example mukavu ====
Since every node in the BST is distinct, we take no action if we discover a value that matches the one we wish to insert.
Node insertion in BST can be carried out in the following ways:
Example
Python:
def insert(node, data):
if node is None:
return TreeNode(data)
else:
if data < node.data:
node.left = insert(node.left, data)
elif data > node.data:
node.right = insert(node.right, data)
return node
Find The Lowest Value in a BST Subtree
A function that locates the lowest value in a node’s subtree is required in order to delete a node from a BST, as will be explained in the following section.
How it works:
1.Commence at the subtree’s root node.
2.As far as you can, move left.
3.The node in that BST subtree with the lowest value is the one you ultimately wind up in.
Assuming that we begin at node 13 in the diagram below and proceed left, we should arrive at node 3, which is the lowest value.
Furthermore, node 14, the lowest value in node 15’s subtree, is reached if we continue leftward from node 15.
==== example mukavu ====
The function that determines the lowest value in a BST node’s subtree looks like this:
Example
Python:
def minValueNode(node):
current = node
while current.left is not None:
current = current.left
return current
In the section that follows, we’ll use the minValueNode() function to determine a node’s in-order successor and utilize that information to remove it.
Delete a Node in a BST
Our program must first look for the node in the BST before deleting it.
There are three situations where removing a node requires a different approach after it has been located.
How it works:
1.Remove the node by eliminating the link to it if it is a leaf node.
2.Connect the parent node of the node you wish to remove to the child node if the node has just one child.
3.In the event that the node has left and right child nodes: Locate the node’s in-order successor, modify its values, and then remove it.
The successor we locate in step 3 above will always be a leaf node; as it is the node that follows the node we wish to remove, we can swap values with it and remove it.
View the deletion of several nodes by using the animation below.
==== example mukavu ====
Node 8 is a leaf node (case 1), so we can simply remove it after we’ve located it.
Node 19 (case 2) has a single child node. Node 18 is directly connected to parent node 15, which allows node 19 to be deleted after that.
Node 13 has two offspring (case 3). By locating the lowest node in node 13’s right subtree, node 14, we may determine the successor, or the node that follows immediately during an in-order traversal. Node 13 is assigned value 14, and node 14 can then be deleted.
The implementation of a BST with the ability to remove a node can be done as follows:
Example
Python:
def delete(node, data):
if not node:
return None
if data < node.data:
node.left = delete(node.left, data)
elif data > node.data:
node.right = delete(node.right, data)
else:
# Node with only one child or no child
if not node.left:
temp = node.right
node = None
return temp
elif not node.right:
temp = node.left
node = None
return temp
# Node with two children, get the in-order successor
node.data = minValueNode(node.right).data
node.right = delete(node.right, node.data)
return node
Line 1: In order to find the node containing the data we wish to delete, the method can run itself recursively on progressively smaller subtrees thanks to the node argument.
Lines 2–8: Here, we are looking for the node that has the correct data that we wish to remove.
Line 9–22: We have located the node that we wish to remove. Three examples of this type of case exist:
Case 1: A leaf node, or node without any offspring. When none is returned, recursion determines the new left or right value for the parent node (line 6 or 8).
Case 2: Node that has a child node on the left or right. By recursion, that left or right child node becomes the new left or right child of the parent (line 7 or 9).
Case 3: The node has children on both the left and the right. The minValueNode() function is used to determine the in-order successor. After setting the successor node’s value to the value of the node we wish to delete, we can delete the successor node without losing its original value.
Line 24: In order to preserve the recursive behavior, node is returned.
BST Compared to Other Data Structures
Binary Search Trees combine the advantages of Linked Lists and Arrays, two additional data structures.
| Data Structure | Searching for a value | Delete / Insert leads to shifting in memory |
|---|---|---|
| Sorted Array | O(logn) | Yes |
| Linked List | O(n) | No |
| Binary Search Tree | O(logn) | No |
Searching a BST is just as fast as Binary Search on an array, with the same time complexity O(logn)
Additionally, just like with linked lists, new values can be added and deleted without causing any memory shifts.
BST Balance and Time Complexity
On a Binary Search Tree, operations like inserting a new node, deleting a node, or searching for a node are actually O(h). That means that the higher the tree is (h), the longer the operation will take.
The reason why we wrote that searching for a value is O(logn)in the table above is because that is true if the tree is “balanced”, like in the image below.
Because there are roughly equal numbers of nodes on the left and right sides of the tree, we refer to this tree as balanced.
When a node’s left and right subtrees have height differences of no more than one, you can be certain that the binary tree is balanced.
The root node’s left subtree in the above image has height h=2., and the right subtree has height h=3..
For a balanced BST, with a large number of nodes (big n), we get height h≈log2n, and therefore the time complexity for searching, deleting, or inserting a node can be written as O(h)=O(logn).
But, in case the BST is completely unbalanced, like in the image below, the height of the tree is approximately the same as the number of nodes, h≈n, and we get time complexity O(h)=O(n)for searching, deleting, or inserting a node.
Therefore, minimizing the height is necessary to perform operations on a Binary Search Tree (BST), and maintaining the balance of a BST is precisely what AVL Trees—the data structure that will be discussed on the following page—do.
