Data Structure - Binary Search Tree - Data Structure & Algorithms

What is Data Structure Binary Search Tree?

A tree in which all the nodes follow some of the properties which are listed below, is a Binary Search Tree (BST).

  • The left sub-tree of a node has a key less than or equal to its parent node's key.
  • The right sub-tree of a node has a key greater than to its parent node's key.

All the sub-trees are divided into two segments – left sub-tree and right sub-tree in BST. The segments are defined by the code -

How a Data Structure Binary Search Tree is represented?

The collection of nodes which are arranged in a manner in which BST properties are maintained is known as BST. Each node possess a key and a value associated to it. The desired key is compared to the Keys available in the BST for searching and if found, the value associated is retrieved.

The pictorial representation of BST is -

Binary Search Tree

It is observed that, the root node key (27) has all less-valued keys on the left sub-tree and the higher valued keys on the right sub-tree.

What are the basic operations supported by Data Structure BST?

The basic operations supported by a BST are -

  • Search − Searches an element in a tree.
  • Insert − Inserts an element in a tree.
  • Pre-order Traversal − Traverses a tree in a pre-order manner.
  • In-order Traversal − Traverses a tree in an in-order manner.
  • Post-order Traversal − Traverses a tree in a post-order manner.

Node

A node with some data is defined, references to its left and right child nodes.

Search Operation

An element is searched from the root node. If the data is less than key value, the element is searched in the left subtree. If not, the element is searched in the right subtree. Same algorithm is followed for each node.

Algorithm

Insert Operation

An element is inserted by locating the proper location. First search the root node, then if the data is less than the key value, search for the empty location in the left subtree and insert the data. Otherwise, search for the empty location in the right subtree and insert the data.

Algorithm


All rights reserved © 2018 Wisdom IT Services India Pvt. Ltd DMCA.com Protection Status

Data Structure & Algorithms Topics