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

Share

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 2i
Maximum number of leaf nodes in a Binary Search Tree of height h is 2h which is  equal to (n+1)/2 , where n is total number of nodes in that BST

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

}