Hello Friends, In this blog post I am going to let you know about how to check whether a given binary tree is Heap, BST(Binary Search Tree), Height balanced tree(AVL Tree), complete binary tree, full binary tree?
Here we are given a binary tree below, and you have to check what type of binary tree is it? And also need to explain the reason for the same.
Consider the binary tree T in fig 1. Observe that T is not a heap. Because neither the largest element in T appears at the top of the heap(max heap) nor the smallest element in T appears at the top of the heap(min-heap).
BST(Binary Search Tree):
Consider the binary T in fig 1. T is not a binary search tree. Because the 60 and 63 are less than the 66 in its right subtree.
Height Balanced Tree(AVL Tree):
Consider the binary tree T in fig 1. T is not a height-balanced tree since the balance factor of node 60 is -2. Each node in a balanced binary tree has a balance of 1, -1, or 0 depending on whether…
… the height of its left subtree is greater than, less than, or equal to the height of its right subtree. The binary T with all its balance factors is shown in Fig 2 below.
Complete binary tree:
Consider the binary tree T in fig 1. T is not a complete binary tree. Since a complete binary tree is a binary tree whose non-leaf nodes have nonempty left and right subtrees and all leaves are at the same level.
Observe that all leaves are not at the same level in fig 1.
Full Binary Tree:
Consider the binary tree T in fig 1. T is not a binary tree. Since, in a full binary tree, every non-leaf nodes have a nonempty left and right subtree. Observe that node 60 and node 4 have no left child.
You can also go through below extensive blog post.
In the case of any queries, you can write to us at [email protected] we will get back to you ASAP.
Hope! you would have enjoyed this post about how to check whether the given binary tree is a heap, binary search tree, AVL tree, complete binary tree, or full binary tree.
Please feel free to give your important feedback in the comment section below.
Have a great time! Sayonara!