Lesson 4: BST (Binary Search Tree) Basic Understandings

Binary Search Tree or BST for short is similar to double linked list that we have discussed in the previous lesson. The only different is the node will link to both (if they have 2 children) child and its parent (if its not on top).

A Perfect BST

Binary Search Tree could be classified into 4 categories which are a perfect tree like you see in the image above, a complete tree, a balanced tree, and a skewed tree.

Balanced Tree

*A perfect tree is always a complete tree but a complete tree is not always a perfect tree

BST can be simply described as an inverted tree because the data or node at the top is called the root and the node at the bottom is called the leafs. We could also use the term grandparent, ancestors, parents, siblings, child and so on.

ex:

• 50 is the ancestor of 67.
• 9 is the sibling of 23.
• The parent of 54 is 76

Properties

The number of maximum node on each level k is 2k.

The number of maximum node on a certain height h is 2h+1 - 1

The maximum height of n nodes is n-1.

The minimum height of n nodes is 2log(n).

Representation of a Binary Tree

Like I said previously, BST is like double linked list but they have multiple pointers that points towards the parent and the children.

Code:

struct node {

  int data;

  struct node *left;

  struct node *right;

  struct node *parent;

};

struct node *root = NULL;

That is binary search tree in the most simplest way to explain it. Next part will be discussing on how to insert new node, delete a certain node and talk about it more deeply into the concept. Thank you for viewing and hope to see you guys in the next post.