Programming Data Structure Binary Search Tree (BST) | Definition and Properties

Binary Search Tree (BST) | Definition and Properties

-

A tree is an abstract data type which store elements hierarchically. With the exception of top element, each element in a tree has a parent element, and zero or more children elements. We generally call the top element root of the tree.

We can represent such a tree by a linked data structure, in which  each node in an object. (Learn linked list, here). In addition to key and satellite data, each nodes contains left, right, and p that point to the nodes corresponding to its left child, right child,  and parent respectively. if a child or parent is missing, the appropriate value contains the null value. The root node is the only node in the tree whose parent is null. 

On average a tree is more efficient if we need to perform many different types of operations. Time needed to perform an operation on a tree is O(log N). Now let’s talk about what is Binary Search Tree (BST).

Binary Search Tree
Fig: Binary Search Tree

Binary Search Tree (BST)

Formally, we define a binary search tree to be a set of nodes storing elements in a parent-child relationship. For binary search tree, every node has maximum two children. middle node is called parent, and less value than parent is the left child, as well as greater value than parent is the right child. In BST, a node might have two maximum number of children. However, a child might have only one child or no child. Node with no child is called leaf.

Binary Search Tree

The reason of using binary search tree that insertion or deletion of elements in the tree is very first. Searching an element in binary search tree is also very first. The binary tree can be balanced or unbalanced.

For an unbalanced tree it might look more like a long list of elements, and less like a tree. Therefore insertion, deletion, or even searching data will no longer be so fast in unbalanced tree. Ordered data normally creates an unbalanced tree. Thus there are algorithms that ensure that our tree stays valid, which is that roughly same amount of nodes will have both left and right side of subtree.

Traversing Of BST

Traversing means visit through trees. There are three way we can visit throughout the tree. 

  • Inorder Traversing – we visit the left node first, then the parent node, and then the right node.
  • Preorder Traversing – Here, we visit the root node first, then the left node, and lastly the right node. 
  • Postorder Traversing – and in postorder traversal we visit the left node first, then the right node, and lastly the parent node or root node.

In BST we typically want to do inorder traversal. Because This allows to print the nodes tree inorder.

Next we will see the implementation of binary search tree here >>

LEAVE A REPLY

Please enter your comment!
Please enter your name here

Latest Articles

Property Decorator | Getters Setters and Deleters in Python

In this article, we will talk about the Property Decorator in Python. It enables the class functionality...

Dictionaries | HashMap in Python | Working with Key-Values

Dictionaries in Python is similar to Hashmap comparing to other languages. It stores data as a key-value...

Hash Table | Indexing | Hashing Algorithm | Python Implementation

This article will talk about a high-level view of the Hash Table. As a programmer, this technique...

Eigenvector Eigenvalue | Linear Algebra Fundamentals

Eigenvector ($bar{v}$) in linear algebra is a non-zero vector (matrix) that doesn't change its direction during linear...

Pivot Table | Microsoft Excel | Create Data Insight Easily

Pivot table in microsoft Excel is an useful function that gives us a way to create insight...

Macro Function in Microsoft Excel | Automate Repetitive Task

This article we will talk about the Macro. It is a function in microsoft excel which basically...

Must read

Dictionaries | HashMap in Python | Working with Key-Values

Dictionaries in Python is similar to Hashmap...

You might also likeRELATED
Recommended to you