Binary trees, Data Structure & Algorithms

Assignment Help:

A binary tree is a special tree where each non-leaf node can have atmost two child nodes. Most important types of trees which are used to model yes/no, on/off, higher/lower, i.e., binary decisions are binary trees.

Recursive Definition: A binary tree is either empty or a node that has left and right sub-trees that are binary trees. Empty trees are represented as boxes (but we will almost always omit the boxes).

In a formal way, we can described binary tree as a finite set of nodes which is either empty or partitioned in to sets of T0, Tl, Tr , where T0 is the root and Tl and Tr are left and right binary trees, respectively.

Properties of a binary tree are following

  • If a binary tree contains n nodes, then it have exactly n - 1 edges;
  • A Binary tree of height h contains 2h - 1nodes or less.
  • If we have a binary tree having n nodes, then the height of the tree is at most n and at least ceiling log2(n + 1).
  • If a binary tree contain n nodes at a level l then, it has at most 2n nodes at a level l+1
  • The total number of nodes in binary tree with depth d (root has depth zero) is

                       N = 20 + 21 + 22 + .......+ 2d = 2d+1 - 1


Related Discussions:- Binary trees

Graph traversal, 1) Which graph traversal uses a queue to hold vertices whi...

1) Which graph traversal uses a queue to hold vertices which are to be processed next ? 2) Which of the graph traversal is recursive by nature? 3) For a dense graph, Prim's a

Explain merge sort, Merge sort: Merge sort is a sorting algorithm that ...

Merge sort: Merge sort is a sorting algorithm that uses the idea of split and conquers. This algorithm splits the array into two halves, sorts them separately and then merges t

Sparse matrix, How sparse matrix stored in the memory of a computer?

How sparse matrix stored in the memory of a computer?

What is a container taxonomy, What is A Container Taxonomy It's useful ...

What is A Container Taxonomy It's useful to place containers in a taxonomy to help understand their relationships to one another and as a basis for implementation using a class

Entity relationship diagram, This question is based on the requirements of ...

This question is based on the requirements of a system to record band bookings at gigs. (A 'gig' is an event at which one or more bands are booked to play). You do not need to know

Quick sort, This is the most extensively used internal sorting algorithm. I...

This is the most extensively used internal sorting algorithm. In its fundamental form, it was invented by C.A.R. Hoare in the year of 1960. Its popularity lies in the easiness of i

Algorithm, Ask question #MWhich of the following is not a characteristic of...

Ask question #MWhich of the following is not a characteristic of good algorithm? inimum 100 words accepted#

Doubly linked list having n nodes, The time required to delete a node x fro...

The time required to delete a node x from a doubly linked list having n nodes is O (1)

Explain internal and external nodes, Explain Internal and External Nodes ...

Explain Internal and External Nodes  To  draw  the  tree's  extension  by  changing  the  empty  subtrees  by  special nodes. The  extra  nodes shown by little squares are know

Determine the importance of array, Determine the importance of array Ar...

Determine the importance of array Arrays are significant since they allow many values to be stored in a single data structure whereas providing very fast access to each value.

Write Your Message!

Captcha
Free Assignment Quote

Assured A++ Grade

Get guaranteed satisfaction & time on delivery in every assignment order you paid with us! We ensure premium quality solution document along with free turntin report!

All rights reserved! Copyrights ©2019-2020 ExpertsMind IT Educational Pvt Ltd