BST

 

Binary  Search Tree:

A Binary Search Tree (BST) is a type of data structure that helps in organizing and managing data efficiently. Here’s a simple explanation of its properties and how it works:

What is a Binary Search Tree?

A Binary Search Tree is a tree structure where each node has at most two children, referred to as the left child and the right child. This type of tree has a specific way of arranging data to make searching, insertion, and deletion operations very efficient.

Properties of a Binary Search Tree

1. Node Arrangement:

   • Each node in a BST contains a key (a value).
   • The left subtree of a node contains only nodes with keys that are less than the node’s key.
   • The right subtree of a node contains only nodes with keys that are greater than the node’s key.

2. Subtree Structure:

   • Both the left and right subtrees of each node must also be binary search trees. This means the rules for arranging nodes apply to every subtree within the tree.

How Does It Work?

Consider you have a BST, and you want to find a particular value. You start at the root node:

• Searching:

  • If the value you are searching for is less than the root’s key, you move to the left child.
  • If it is greater, you move to the right child.
  • You repeat this process until you find the value or reach a leaf node (a node with no children).

• Insertion:

  • To insert a new value, you follow the same logic as searching.
  • Starting at the root, you move left or right depending on whether the new value is less than or greater than the current node’s key.
  • When you find an appropriate empty spot (where a child node would be null), you insert the new value there.

• Deletion:

  • Deleting a node from a BST requires a bit more thought:
    • If the node is a leaf, you can simply remove it.
    • If the node has one child, you remove the node and replace it with its child.
    • If the node has two children, you need to find the in-order successor (the smallest node in the right subtree) or the in-order predecessor (the largest node in the left subtree), replace the node's key with this successor’s (or predecessor’s) key, and then delete the successor (or predecessor)

Inorder Traversal:

 

At first traverse left subtree then visit the root and then traverse the right subtree.

Follow the below steps to implement the idea:

·         Traverse left subtree

·         Visit the root and print the data.

·         Traverse the right subtree

Program:

// C++ code to implement the approach

 //Inorder

#include <bits/stdc++.h>

using namespace std;

 

// Class describing a node of tree

class Node {

public:

    int data;

    Node* left;

    Node* right;

    Node(int v)

    {

        this->data = v;

        this->left = this->right = NULL;

    }

};

 

// Inorder Traversal

void printInorder(Node* node)

{

    if (node == NULL)

        return;

 

    // Traverse left subtree

    printInorder(node->left);

 

    // Visit node

    cout << node->data << " ";

 

    // Traverse right subtree

    printInorder(node->right);

}

// Driver code

int main()

{

    // Build the tree

    Node* root = new Node(100);

    root->left = new Node(20);

    root->right = new Node(200);

    root->left->left = new Node(10);

    root->left->right = new Node(30);

    root->right->left = new Node(150);

    root->right->right = new Node(300);

    // Function call

    cout << "Inorder Traversal: ";

    printInorder(root);

    return 0;

}

 Output: