Question

What is a binary search tree or BST? Discuss its characteristics. What are other types of binary trees as well?

Answer 1

Binary Search Tree: It is one of the data structures. And it is node-based.

Characteristics of Binary Search tree:

1. The left subtree of a node contains only nodes with keys lesser than the node’s key.
2. The right subtree of a node contains only nodes with keys greater than the node’s key.
3. The left and right subtree each must also be a binary search tree.

Example:

Explanation :

Here the root node is 8.And Left of 8 is 3 which is less than the root node.And Right of 8 is 10 which is greater than root node.So,here 1st and 2nd characteristics are true.

Now , Take the node 3.Left of 3 is 1 which is less than the 3.And Right of 3 is 6 which is greater than the 3.

Types of Binary Tree :

1. Full Binary Tree : The binary tree is called full binary tree if every node has 0 or 2 children.

Example:

Here every node has 2 childrens except leaf nodes.Leaf nodes are nothing but the left and right child nodes are null.Null means 0 children.Here 3 ,6,7 are leaf nodes.

2.Complete Binary Tree : A Binary Tree is a Complete Binary Tree if all the levels are completely filled except possibly the last level and the last level has all keys as left as possible.

Example :

Here all the levels are filled but not the last level and in last level the more nodes are in left.

3.Perfect Binary Tree : A Binary tree is a Perfect Binary Tree in which all the internal nodes have two children and all leaf nodes are at the same level.

Here each node has 2 childrens and all the lead nodes are at same level i.e.,level-5.

4. A degenerate tree : A Tree where every internal node has one child.It is also called pathological tree.

Here every internal node has one child.