GATE CSE
First time here? Checkout the FAQ!
x
+2 votes
159 views

What is the difference between

Binary Tree and Almost complete Binary tree and complete Binary Tree and full Binary Tree and Binary search Tree and Balanaced Binary Search Tree. 

Diagram would be appriciated otherwaise write 2-3 basic difference .

asked in DS by Active (1.8k points)   | 159 views

3 Answers

0 votes

Binary tree :- Any tree with max two child nodes

Full Binary tree:- Any tree with a given level h having 2^h-1 elements

complete binary tree : if we start removing elements from full binary tree ( 0 or more from rightmost leaf node )result will always be a CBT 

almost CBT : it is a complete binary tree in which  last level is not full (i.e at least one element has to be removed from full binary tree)

 

BST  is based on values values in left are less than root and values at right are more than root

e.g  

         30

12              45

for balanced BST refer

https://www.cpp.edu/~ftang/courses/CS241/notes/self%20balance%20bst.htm

answered by Veteran (37.5k points)  
edited by
@snajay sir is it allowed in almost CBT to have all the childrens on the RHS parent without filling up Left parent .
no left child must be there for corresponding right child but converse is not true e.g following tree is not almost CBT

               A

                      c

                 d           e
but in your paper pen explanation first exp from bottom it has lest child but no right chile . but on the next parent node you have given both child without filling up previous right child of lest node
Ya in bottom last part how can we show both left child as well right child of parent until unless we dnt put right child of  parent being at the same level
thanks edited now
0 votes
courses.cs.vt.edu/~cs3114/Fall09/wmcquain/Notes/T03a.BinaryTreeTheorems.pdf

i think u should give it a try.
answered by Active (2.1k points)  
0 votes

In above are the types of binary tree

answered by Boss (9.2k points)  
edited by
Top Users Jan 2017
  1. Debashish Deka

    7172 Points

  2. Habibkhan

    4696 Points

  3. Vijay Thakur

    4308 Points

  4. sudsho

    4090 Points

  5. saurabh rai

    4024 Points

  6. Arjun

    3292 Points

  7. santhoshdevulapally

    3066 Points

  8. GateSet

    3016 Points

  9. Bikram

    3014 Points

  10. Sushant Gokhale

    2892 Points

Monthly Topper: Rs. 500 gift card

18,838 questions
23,808 answers
51,589 comments
20,148 users