Binary Search Trees (BST) - I

Binary search trees also called ordered or sorted binary trees, are a particular type of Binary Trees that follows the following properties:

• All the nodes in the left subtree of an internal node have smaller values than that of the node.
• All the nodes in the right subtree of an internal node have greater values than that of the node.
• Both left and right subtrees must also be Binary search Trees.

Inserting a Node in a BST

While inserting a node in a binary search tree, we must follow the properties of a BST. Let’s say we have the following BST, and we have to insert a node with the value 22.

1. To find its correct position we:
2. Start from the root node.
3. Compare its value with the value of the node to be inserted.
4. If the value at the current node is smaller, move on to its right subtree; else, move to its left subtree.
5. If you hit NULL, insert the new node there as a left/right child depending on the value.

CODE:

``` C++ class TreeNode{ int val; TreeNode left; TreeNode right; TreeNode(int data){ val = data; left = NULL; right = NULL; } };

TreeNode Insert(TreeNode root,int val){ if(root == NULL) //If we hit a NULL we insert our new Node there. //If the tree is empty it returns the new node as the root. return new TreeNode(val)

if(val > root->val)
//Move on to the right subtree..
root->right = Insert(root->right,val);

else 
//Move on to the left subtree
root->right = Insert(root->left,val);

// After inserting the new Node, return the original root.

// If the node of the same value is present in the tree, it simply
// returns and prevents from inserting duplicates.
return root;

} ```

Time complexity: In the worst-case scenario, we have to travel to the deepest node. The time complexity in which case will be O(h) where h is the height of the tree. However, in the case of a skewed tree where are all the nodes have either one child or no child, the height will be equal to the number of nodes in the tree, thus making the time-complexity O(n).

Searching a Node in a BST

We have seen BFS and three types of DFS that we use to search a general tree. Since the BST follows some unique properties, they can be exploited to search a value in the tree faster and more efficiently.

Let’s say we have the following BST, and we have to search the node with the value 9.

1. Start from the root node.
2. Compare its value with the value we are looking for.
3. If the value of the current node is equal to that, we stop our search here.
4. If the value at the current node is smaller, move on to its right subtree; else, move to its left subtree.
5. If we hit a NULL, that indicates the value is not present in the tree.

CODE:

bool search(TreeNode* root,int val){
    if(!root) return false;

    if(root->val == val) return true;

    if(val > root->val)
    //Look for the value in right subtree
    return search(root->right,val);

    else 
    //Look for the value in left subtree
    return search(root->left,val);
}

Time complexity: Like insertion, we have to travel to the deepest node in the worst-case scenario. The time complexity in which case will be O(h), h being the height of the tree, and in a skewed tree, time-complexity will be O(n).

Comparing this to the Time complexity of searching in a general tree which is always O(n) in the worst case, searching in this tree is faster.

Verification of a BST

Many times, we are asked to verify that the given tree is a BST or not. To do this task, we just traverse the tree and verify two things:

1. If an internal node is a left child of its parent, its value should be smaller than the parent. Here, we make a common mistake by checking just this. But we also need to make sure that all the nodes below this internal node must also be smaller than the parent. Similarly, if the internal node is a right child, its value along with the value of all its children must be greater than its parent.
2. If the above is true we check that both its subtrees are BSTs or not.

CODE:

bool verify(TreeNode *root, int minVal, int maxVal) {    
    if (root== NULL) return true;    
    if (root>val < minVal || root->val > maxVal) return false;        
    return verify(root->left, minVal, root->val-1) && verify(root->right, root->val+1, maxVal);
}

NOTE: In the initial function call, the minVal and the maxVal will be INT_MIN and INT_MAX.

Application of BST

1. Sorting: BST can be used to sort as the in-order traversal of it gives a sorted array. Try it!
2. Priority queues: BST can be used to find the minimum value or the maximum value in the tree easily since the leftmost node is minimum and the rightmost node is maximum.

We shall come up with more on the Binary search Tree in the next article. Keep reading Batoi Developers Blog and stay safe!