Binary Search Tree

Binary Search Tree:

GFG

Binary Search Tree is a node-based binary tree data structure which has the following properties:

  • The left subtree of a node contains only nodes with keys lesser than the node’s key.
  • The right subtree of a node contains only nodes with keys greater than the node’s key.
  • The left and right subtree each must also be a binary search tree.

Number of trees:

although the number of permutations of numbers is but those permutations output similar trees so the number of different trees is less than and equal to:

Inserting a element:

When inserting a new node into a binary search tree, we follow these steps:

  1. Start at the root of the tree.
  2. If the tree is empty, the new node becomes the root.
  3. If the new node's value is less than the current node's value, move to the left child.
  4. If the new node's value is greater than the current node's value, move to the right child.
  5. Repeat steps 3 and 4 until a suitable empty position is found.
  6. Insert the new node in that position.