Binary Search Tree - Time Complexity and Data Structure

By Priyanshu Vaish|Updated : May 11th, 2022

Binary Search Tree: The binary search tree is the advanced algorithm used for analyzing the node and its left and right branches, which are modeled in a tree structure and return the value. A binary search tree, also known as an ordered or sorted binary tree in computer science, is a rooted binary tree data structure whose internal nodes each hold a key that is higher than all the keys in the node's left subtree but less than those in the node's right subtree.

The Binary Search Tree (BST) is devised on the architecture of the basic binary search algorithm. Hence it enables faster lookups, insertions, and removals of nodes. Further, we will discuss the time complexity of binary search tree, data structure, abstract data type, and a lot more in the upcoming sections.

Table of Content

What is a Binary Search Tree?

A binary search tree (BST) is the binary tree where each node has a Comparable key (and an associated value) and satisfies the restriction that the key in any node is larger than the keys in all nodes in that node's left subtree and smaller than the keys in all nodes in that node's right subtree.

  • Node x
  • Data in Left(x) is less than x
  • Data in Right(x) is greater than x
  • Notation: Key(x) means the data is in Node x.

byjusexamprep
Expression Trees
(a) (a + (b×c)) + (((d×e) + f)×g)
(b) General evaluation strategy: inorder traversal
      Left, Op, Right
(c) Postorder:
      Left, Right, Op
(d) Preorder:
     Op, Left, Right

What is an ADT for a Binary Search Tree?

BST(Binary Search Tree) as Abstract Data Type. There are many functions that are as follows:

  • Insert(x)        // Insert item
  • Find(x)          // find item
  • Delete(x)       // delete item
  • Traverse()     // visit nodes in tree (several different ways)
  • Minimum()    // find minimum
  • Maximum()   // find maximum
  • Successor(x) // find x's successor

Data Structure of a Binary Search Tree

The data structure and pseudocode of the binary search tree are as follows

struct Node
{
int data;
Node*left;
Node*right;

};

Keep a pointer called "root" to the tree.
All you need to maintain is node root to access any nodes in the tree!
This is like a linked list. Remember, for the linked list, we only need to store the "head" pointer.
Reminds you of a linked list? Remember, X = X → next;
Now we have:
if(x → left)
x= x → left: (more to left)
if(x → right)
x= x → right: (more to right)

What is a Skew Binary Search Tree?

When the height of a BST goes till 'n' with 'n' elements, the tree is said to be skew BST. There are two types of skew binary search trees:

1. Left skewed BST
2. Right skewed BST

byjusexamprep

Searching the Tree

The pseudocode of the binary search tree is as follows: 

Search(x, k)
Check if "k" is in the Tree.
Algorithm Search(x, k)
Input: x is the tree's root, and k is the input search key.
Output the node containing k or NULL
1. while x ≠ NULL
2. do if k = key(x)
3. then return x;
2. else
5. if k < key(x)
6. then x:= left(x);
7. else x:=right(z);
8. return NULL;
Running time = O(tree height)

Example: Search(root 17)

byjusexamprep

X==NULL
Stop... Not found

How to Find Minimum and Maximum in a Binary Search Tree?

The leftmost node of the BST(binary search tree) is always the minimum element. The rightmost node of the BST(binary search tree) is always the maximum element. The time complexity of the worst case is the height of the tree.
Algorithm Minimum(x)
Input: x is the root
Output: the node containing the minimum key
1. while left(z) ≠ NULL
2. do x:=left(z)
3. return x;
Algorithm Maximum(x)
Input: x is the root
Output: the node containing the maximum key.
1. while right (x) ≠ NULL
2. do x:=right (x)
3. return x;

Successor in Binary Search Tree

The successor of the node x in a binary search tree is defined as a node y, whose key(y) is the successor of key(x) in sorted order of the tree.

Three Scenarios to Determine Successors:
Scenario-1:

  • Node x has the right subtree.
  • By definition of BST(binary search tree), all items greater than x are in this right sub-tree.
  • The successor is the minimum (right(x)).

Scenario-2:

  • Node has no right subtree,
  • X is the left child of the parent(X).
  • The successor is the parent(X)
  • The successor is a node whose key would appear in the next sorted order. Think about in order traversal.   

byjusexamprep

byjusexamprep

Scenario-3:
Node x is not a left child of the immediate parent.
Keep moving up the tree until you find the parent which branches from the left().
Must traverse up the tree until we find a suitable parent
Stated as in Pseudocode:
y parent (x);
while y ≠ NULL and x=right (y)
do x:=y:
x-parent (y);

byjusexamprep
Algorithm Successor(x)
Input: x is the input node.
1. if right (x) ≠ NULL
2. then return Minimum (right (x)); [Scenario-1]
3. else
4. y:=parent (x);
5. while y ≠ NULL and x-right (y)
6. do x:=y; (Scenario-2 and 3)
7. y:=parent (y);
8. return y;

Successor (r, x)
Input: r is the tree's root, and x is the node.
1. initialize an empty stack S;
2. while key (r) #key (x)
3. do push(s, r);
4. if key (x) < key (r)
5. then r:=left (r);
6. else r:=right (r);
7. if right (x)  ≠  NULL
8. then return Minimum (right (x));
9. else
10. if s is empty
11. then return NULL;
12. else
13. y:=pop (S);
14. while y# NULL and x=right (y)
15. do x:=Y ;
16. if s is empty
17. then y:=NULL;
18. else y:=pop (S);
19. return Y;

Comments

write a comment

FAQs on Binary Search Tree

  • A binary search tree is the data structure that quickly allows us to maintain the sorted list of numbers. It is called binary tree because each tree node has the maximum of two children.

  • A Binary Tree is the non-linear data structure in which a node can have 0, 1 or 2 nodes. Individually, each node consists of a left pointer, right pointer and data element. But Binary Search Tree is an organized binary tree with a structured organization of nodes. Each subtree must also be of that particular structure

  • The tree is considered balanced because the difference between the left subtree and right subtree heights is not more than 1.

  • An unbalanced binary tree is not balanced. A complete binary tree has all levels filled, except possibly the last. If a complete tree has maximum depth n, it has at least 2n and at most 2n+1−1 nodes. A complete tree with exactly 2n+1−1 nodes is called perfect.

  • The benefits of a binary search trees are as follows.

    • Reflect structural relationships that exist in the given data set.
    • Make insertion and deletion faster than linked lists and arrays.
    • A flexible way of holding and moving data.
    • Are used to store as many nodes as possible.
  • A balanced binary search tree is a binary search tree. The binary search tree's height becomes log (n). As a result, the time complexity of BST operations is O(logn).

Follow us for latest updates