Binary​ Search Trees

Objectives

    1. Why Binary Search Trees

    2. Operations on Binary Search Trees

    3. Finding an element in Binary search tree

    4. Inserting an element in Binary search tree

    5. Deleting an element from Binary search tree

    6. Exercise

        a. Challenge 1 (Silver Badge)

        b. Challenge 2 (Gold Badge)

1.Why Binary Search Trees

In the previous recitation we discussed different tree representations and in all of them we did not impose any restriction on the node data. As a result, to search for an element we need to check both in left subtree and in right subtree. Due to this, the worst case complexity of search operation is O(n).

In this class, we will discuss another version of binary trees. Binary Search Trees(BSTs). As the name suggests, the main use of this representation is for searching. In this representation, we impose restriction on the kind of data a node can contain. As a result, it reduces the worst-case runtime for search from O(n) to O(logn) (in case of balanced BSTs).


Binary search tree property

In binary search trees, all the left subtree elements should be less than root data and all the right subtree elements should be greater than root data. This is called binary search tree property. Note that this property should be satisfied at every node in the tree.

    • The left subtree of a node contains only nodes with keys less than the node’s key.

    • The right subtree of a node contains only nodes with keys greater than the node’s key.

    • Both the left and right subtrees must also be binary search trees.























Binary Search Tree Declaration

There is no difference between regular binary tree declaration and binary search tree declaration. The difference is only in data but not in structure.


2.​Operations on Binary Search Trees
Following are the main operations that are supported by binary search trees:


Main Operations:

    • Find/ Find Minimum / Find Maximum in binary search trees

    • Inserting an element in binary search trees

    • Deleting an element from binary search trees




Auxiliary Operations:

    • Checking whether the given tree is a binary search tree or not.

    • Finding kth smallest element in tree.

    • Sorting the elements of binary search tree and many more.


Tip: Since root data is always between left subtree and right subtree data, performing inorder traversal on binary search tree produces a sorted list.




3.​Finding an element in Binary Search Trees
Find operation is straightforward in a BST. Start with the root and keep moving left or right using the BST property. If the data we are searching is same as nodes data then we return current node. If the data we are searching is less than nodes data, then search left subtree of current node; otherwise search right subtree of current node. If the data is not present, we end up in a null​link.



struct node* ​find​(struct node* root, ​int​ value)
{
​// root is null or key is present at root
if​​ (root == NULL​​ || root->data == value)
​return​ root;

​// Value is greater than root's key
if​​ (root->data < value)
​return​ find(root->right, value);

​// Value is smaller than root's data
return​​ find(root->left, value);
}






4.​Inserting an element into Binary Search Tree
For inserting a node into a BST is that, we start from the root node, if the node to insert is less than the root, we go to left child, and otherwise we go to the right child of the root. We continue this process (each node is a root for some sub tree) until we find a null pointer (or leaf node) where we cannot go any further.




We then insert the node as a left or right child of the leaf node based on whether the node is lesser or greater than the leaf node. We note that a new node is always inserted as a leaf node​. If a tree is empty, this new node becomes the root.

A recursive algorithm for inserting a node into a BST is summarized as follows:

    1. Start from root.

    2. Compare the element that is getting inserted with the root, if it is less than root, then recurse in the left, else recurse in the right side.

    3. After reaching end, just insert that node at left, if less than current else right.



5. Deleting an element from Binary Search Tree

Deleting a node could affect all subtrees of that node. So we need to be careful about deleting nodes from a tree. We should delete an element by without violating the Binary Search Tree property! The best way to deal with deletion seems to be considering special cases. We

Case 1: Deleting a leaf node:

If the node to be deleted is a leaf node: return NULL to its parent. That means make the corresponding child pointed NULL.

Case 2: Deleting a node with one child:

If the node to be deleted has one child: In this case we need to send the current nodes child to its parent.

If the node to be deleted has a left child - Send that left child to the parent of the deleted node.

The deleted node’s parent will adopt its left child.

If the node to be deleted has a right child - Send that right child to the parent of the deleted node. The deleted node’s parent will adopt its right child.



Case 3: Deleting a node with two children:


This is a tricky case as we need to deal with two subtrees!

First we find a replacement node for the node to be deleted. We need to do this while maintaining the BST order property. Then we copy​ the data of the replacement node to the node to be deleted and delete the replacement node. (Now the deletion may recursively reduce to either Case 1, or Case 2 )

How do we find the replacement node?

Search the data from the subtree of node to be deleted and find the node whose data when placed at the place of node to be deleted will keep the Binary Search Tree property(key in each node must be greater than all keys stored in the left subtree, and smaller than all keys in right subtree) intact.

If the node to be deleted is N, find the largest node in the left sub tree of N or the smallest node in the right subtree of N. These are two candidates that can replace the node to be deleted without losing the order property.


For example, consider the following tree and suppose we need to delete the node with data 20.



6. Time Complexity of BST Operations



What is a Balanced BST and why do we need them?

Each of the BST operation we have seen so far - doing lookup, insertion and deletion, the cost of our algorithms is proportional to the height of the tree. Height of a tree is same as height of the root. Height of a node is the longest path from the node to any leaf.

If the BST is built in a “balanced” fashion, it maintains h = O(log n) ⇒ all operations run in O(log n) time. Let’s see how a “balanced” BST with ​n ​nodes has a maximum order of ​log(n) levels!

Consider an arbitrary BST of the height h. We then count nodes on each level, starting with the root, assuming that each level has the maximum number of nodes. The total possible number of nodes is given by:

n = 1 + 2 + 4 + ... + 2h​-1​+ 2h​​= 2h+1​​- 1


Solving this with respect to h, we obtain,

h = O(log n)

where the big-O notation hides some superfluous details.

If the data is randomly distributed, then we can expect that a tree can be “almost” balanced, or there is a good probability that it would be.​ ​However, if the data already has a pattern, then just naïve insertion into a BST will result in unbalanced trees. Imagine starting with an empty tree and inserting 1, 2, 3 and 4, in that order.





We do not get a branching tree, but a linear tree. All of the left subtrees are empty. Because of this behavior, ​in the worst case​each of the operations takes time ​O​(​n​). From the perspective of the worst case, we might as well be using a linked list and linear search. Therefore, a great care needs to be taken in order to keep the tree as balanced as possible.

Exercise

You can always use helper functions to perform recursion. We are using them in this exercise too.

        A. Silver Badge Problem

            1. Download the ​zip ​files from Moodle, it has header and implementation files on BST.
            2. Given a range, ​removeRange()​function deletes all keys in the BST which are in the given range. Complete the TODOs in the ​deleteNode()​function in ​BST.cpp​.





    B. Gold Badge Problem

            1. Complete the ​isValidBST() ​function in the ​BST.cpp ​file​.
            2. Given a root of a binary tree, ​isValidBST()​should return ​true​if the tree is a valid BST, else return ​false​.