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

Creation of Heap, Q. Create a heap with the given list of keys: ...

Q. Create a heap with the given list of keys: 8, 20, 9, 4, 15, 10, 7, 22, 3, 12                                                  Ans: Creation

Small program on Algorithms , Objective The goal of this project is to ext...

Objective The goal of this project is to extend and implement an algorithm presented in the course and to apply notions introduced by the course to this program/algorithm. The ass

Worst case and average case, Worst Case: For running time, Worst case runn...

Worst Case: For running time, Worst case running time is an upper bound with any input. This guarantees that, irrespective of the type of input, the algorithm will not take any lo

Time required to delete a node x from a doubly linked list, The time needed...

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

Process of post-order traversal, Post-order Traversal This can be done ...

Post-order Traversal This can be done both iteratively and recursively. The iterative solution would need a change of the in-order traversal algorithm.

Delete a given node from a doubly linked list, Algorithm to Delete a given ...

Algorithm to Delete a given node from a doubly linked list Delete a Node from Double Linked List DELETEDBL(INFO, FORW, BACK, START, AVAIL,LOC) 1. [Delete Node] Set FOR

Advantage of list over arrays, The advantage of list over Arrays is flexibi...

The advantage of list over Arrays is flexibility. Over flood is not a problem until the computer memory is bushed. When the individual record are quite large, it may be difficult t

Pipeling, Asktypes of pipelining question #Minimum 100 words accepted#

Asktypes of pipelining question #Minimum 100 words accepted#

Ways to implement abstract data types, Ways to implement abstract data type...

Ways to implement abstract data types A large part of the study of data structures and algorithms is learning about alternative ways to implement an ADT and evaluating alternat

Create algorithm for similarities between documents, Here is a diagram show...

Here is a diagram showing similarities between documents; this is an actual set of physics lab assignments from a large university. Each node (square) in the graph is a doc

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