Binary Search Tree: Explanation

Board Infinity -

What is Binary Tree Data Structure?

A Binary Tree is a Tree data structure with no more than two children. Because each element in a binary tree can only have two children, they are commonly referred to as the left and right child.

Binary Tree Representation

A pointer to the tree's topmost node represents a Binary tree. If the tree is empty, then the root value is NULL.

A Binary Tree node is made up of the following components:

  1. Data
  2. Pointer to the left child
  3. Pointer to the right child

Basic Binary Tree Operation

  • Adding a new element.
  • Deleting an element.
  • Searching for an element.
  • Traversing an element.

Auxiliary Binary Tree Operation

  • Determining the tree's height
  • Determine the tree's level.
  • Determining the overall size of the tree.

Applications of Binary Search Tree (BST):

Because BSTs are organized, they can be used for many different things.

  • BSTs are utilized in indexing as well as multi-level indexing.
  • They are also useful in the implementation of various search algorithms.
  • It is helpful for maintaining a stream of sorted data.
  • Self-balancing BSTs are used internally to implement the TreeMap and TreeSet data structures.

Binary Search Tree: Transversal

Three different types of traversals can be made over a binary search tree. All of these traversals follow a largely similar path through the tree's nodes.

In-order

The root node's left subtree is traversed first, then the current node, and finally the right subtree of the current node. The base case, which states that an empty tree is also a binary search tree, is also represented by the code.

Syntax:

void inOrder(struct node* root) {
        // Base case
        if (root == null) {
                return;
        }
        // Travel the left sub-tree first.
        inOrder(root.left);
        // Print the current node value
        printf("%d ", root.data);
        // Travel the right sub-tree next.
        inOrder(root.right);
}

Pre-order

This traversal initially reads the current node value before traversing the left and right sub-trees.

Syntax:

void preOrder(struct node* root) {
        if (root == null) {
                return;
        }
        // Print the current node value
        printf("%d ", root.data);
        // Travel the left sub-tree first.
        preOrder(root.left);
        // Travel the right sub-tree next.
        preOrder(root.right);
}

Post-order

This traversal runs over the left and right subtrees first, then the root value. The order of the left and right subtrees remains unchanged. In all of the preceding traversals, just the position of the root changes.

Syntax:

void postOrder(struct node* root) {
        if (root == null) {
                return;
        }
        // Travel the left sub-tree first.
        postOrder(root.left);
        // Travel the right sub-tree next.
        postOrder(root.right);
        // Print the current node value
        printf("%d ", root.data);
}

write your code here: Coding Playground