Last Updated on December 14, 2022 by Prepbytes
Binary Tree:
A Binary tree is a tree data structure in which each node has at most two children i.e. the left child and right child.
Representation: A binary tree is represented by a pointer to the topmost node i.e. root node or parent node and if the tree is empty, then the value of the root node is NULL.
Parts of the Binary tree:
- Data
- Pointer to the left child
- Pointer to the right child
Traversal of a Binary Tree:
-
Depth-first traversal:
- Inorder Traversal (Left-Root-Right)
- Preorder Traversal (Root-Left-Right)
- Postorder Traversal (Left-Right-Root)
-
Breadth-first traversal:
- Level order traversal
Basic Operations on Binary Tree:
- Inserting an element
- Removing an element
- Searching an element
- Traversing an element
Binary Tree Traversals:
- Inorder Traversal: Left-Root-Right i.e. The left node is traversed first then the root node and then the Right node.
- Preorder Traversal: Root-Left-Right i.e. The Root node is traversed first then the left node and then the right node.
- Postorder Traversal: Left-Right-Root i.e. The Left node is traversed first then the right node and then the Root node.
Binary Search Tree(BST):
A Binary Tree is a tree-based data structure with the following properties:
- The Left subtree of a tree only contains the nodes which are lesser than the root node.
- The right subtree of a tree only contains the nodes which are greater than the root node.
- And the same for the left and right subtree.
Basic Operations on Binary Search Tree:
- Inserting an element
- Removing an element
- Searching an element
- Traversing an element
Binary Search Tree Declaration / Syntax:
struct BinarySearchTree{
int data;
struct BinarySearchTree<em> left;
struct BinarySearchTree</em> right;
};
Binary Heap:
A Binary Heap is a complete binary tree that follows a heap ordering property. The representation is done as:
Parent Node: (i-1)/2
Left Child: (2i) + 1
Right Child: (2i) + 2
The above table shows the indexes of the ith node.
Hashing:
Hashing is a technique that is used for storing and retrieving data in a faster manner. The most popular use of hashing is the implementation of a hash table.
A hash table stores a key and a value pair in a list which is accessible through its index.
A Hash function generates the new value according to a mathematical hashing algorithm known as a hash.
Hash tables support operations like:
- Insert
- Get
- Delete
This article tried to discuss the concept of binary tree, bst, heap, and hash. Hope this blog helps you understand the concept. To practice problems on Heap you can check out Data Structures and Algorithms.