> For the complete documentation index, see [llms.txt](https://soumyajit4419.gitbook.io/ds-algo/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://soumyajit4419.gitbook.io/ds-algo/binary-tree/terminology-and-formula.md).

# 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.**

![](https://1416717093-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-ME49AWTsL3PV5O3FW36%2F-MFg5iCy32mSgQAU00vQ%2F-MFg7TMYHq_RLSUGtKf_%2Ffull-binary-tree_0.png?alt=media\&token=a84d4c50-4f42-4bca-b95e-c4bbee844227)

## 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.

![](https://1416717093-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-ME49AWTsL3PV5O3FW36%2F-MFg5iCy32mSgQAU00vQ%2F-MFg8IShCnYqH7Znjiwy%2Fcomplete-binary-tree_0.png?alt=media\&token=760e9f6b-a2b4-41ee-800b-012644183055)

## 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.**

![](https://1416717093-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-ME49AWTsL3PV5O3FW36%2F-MFg5iCy32mSgQAU00vQ%2F-MFg7vZGV35B88jr7AY-%2Fperfect-binary-tree_0.png?alt=media\&token=a94c92e4-c032-47bb-a528-928af3079e88)

## **Balanced Binary Tree / H**eight-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.**

![](https://1416717093-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-ME49AWTsL3PV5O3FW36%2F-MFg5iCy32mSgQAU00vQ%2F-MFg9Lgq2omKRWyO8u3d%2Fbalanced-binary-tree.png?alt=media\&token=5f7deca3-fa43-48d4-8a7c-b483b335c408)

## 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.**