# What is a Binary Search Tree, related definitions and properties ?

**Recommended to visit after going through this article:**

**How to insert a node in a Binary Search Tree ?**

**How to search a node in a Binary Search Tree ?**

**How to delete a node in a Binary Search Tree ?**

**Binary Search Tree:** A Tree is said to be a Binary Search Tree if it possess the following properties –

1. It is a Binary Tree.

2. Every Node in it has a value ( also known as a **key** )

-always greater than the value of all nodes present in its left sub-tree

-always lesser than the value of all nodes present in its right sub-tree

Note: A Binary Search Tree is also sometimes called as an **Ordered Binary Tree**.

**Some important Definitions:**

**Depth of a Node : ** is the number of edges from the node to the root node.

**Height of a Node :** is the number of edges from the node to the deepest leaf. When someone says find the height of a binary search tree – they mean finding the height of the root node.

**Degree of a Node :** is the number of children it has – in a binary search tree the degree of a node can be zero, one or two.

**Some important properties :**

Maximum number of nodes in a Binary Search Tree at any given level **i is ****2 ^{i}**

Maximum number of leaf nodes in a Binary Search Tree of height

**h**is

**2**, where n is total number of nodes in that BST

^{h}which is equal to (n+1)/2**Generally, in an Object Oriented programming language like Java a binary search tree is represented using a class Node as shown below –**

Node.java

public class Node { private int data; // also called as a key private Node leftNode; private Node rightNode; // getters and setters for the above // properties }