Terminology and Formula

Height :

In a tree data structure, the total number of edges from leaf node to a particular node/root is called as HEIGHT. I.E (Down to Up)

Depth :

In a tree data structure, the total number of egdes from root node to a leaf/particular node is called as DEPTH of that Node. I.E ( Up to Down)

Strict/Full Binary Tree

A binary tree in which every node has either two or zero number of children is called Strict Binary Tree.

Strict binary tree is also called as Full Binary Tree.

Complete Binary Tree

A complete binary tree is a binary tree in which all the levels are completely filled except possibly the lowest one, which is filled from the left.

A complete binary tree is just like a full binary tree, but with two major differences:

1. All the leaf elements must lean towards the left.

Perfect Binary Tree

A perfect binary tree is a type of binary tree in which every internal node has exactly two child nodes and all the leaf nodes are at the same level.

Balanced Binary Tree / Height-Balanced binary tree

A balanced binary tree, also referred to as a height-balanced binary tree, is defined as a binary tree in which the height of the left and right subtree of any node differ by not more than 1.

Binary Search Tree(BST)

The properties that separate a binary search tree from a regular binary tree is:

1. All nodes of left subtree are less than the root node

2. All nodes of right subtree are more than the root node

3. All nodes must be distinct

• It is called a search tree because it can be used to search for the presence of a number in O(log(n)) time.

AVL Tree

AVL tree is a self-balancing binary search tree in which each node maintains extra information called a balance factor whose value is either -1, 0 or +1.