Binary Trees

Binary Tree:

A binary tree (T) is defined as a set of elements called nodes such that:

  1. T is empty (called the empty tree or null tree), or
  2. T contains a distinguished node R, called the root of T, and the remaining nodes of T form an ordered pair of disjoint binary trees T1 and T2.

This implies that a binary tree could have just a Root node, or it could have a root node and a empty T1 but a concrete T2 and so on.

The height of the empty binary tree is -1. The level (which starts from 0) is also referred to the depth of that element. The height of the nonempty binary tree is the depth of the farthest leaf.

2-Tree, Full and Complete Binary Tree:

A binary tree is a 2-tree if each node N has either 0 or 2 children. 

A binary tree is full if

  • T is empty or
  • There is a distinguished node R with either 0 or 2 children. This implies that the height of the children is the same.

A complete binary tree is full till the next to last level and the lowest level has leaves farthest to the left. All full binary tress are complete but the converse is not true.

For a complete binary tree, we have the following formulaes:

  • The maximun no of elements => 2^(i+1) -1 where i = height of the tree.
  • The maximum no of nodes at a particular level =  2^k where k represents the level

Memory Representation: 

A binary tree can be represented in the memory in the following ways:

  1. As a linked list.
  2. As an indexed array.

I would prefer the indexed array for a complete or a nearly complete binary tree since access time to look up the children of any node is constant. If the tree is far from complete then space would be wasted and this approach would not meet the space requirements for an algorithm.

For instance, in case of the array:

  • The root node is at Tree[0]
  • For a node at Tree[k], the left child if any is at Tree[2*k+1] and the right child if any is at [2*k+2]

 External Path Length of a binary tree:

It is the sum of all root to leaf path lenghts. Formally:

If t is a non empty binary tree, then the external path length E(t), is the sum of the depths of all leaves in that tree. This result is important for sorting algorithms.

TODO: the external path length (E(t) >= (k/2) floor(logk) proof.

 Traversals:

InOrder

Characterized by LNR (Left, Node, Right). It gets its name from the fact that for the binary search tree, this algo will traverse the elements in order (ascending)

PreOrder (also called DFS)

Characterized by NLR. It produces the prefix notation. To implement iteratively use a stack and then push right tree and then left tree. Note that the order of pushing is reversed.

PostOrder

Characterized by LRN. Produces the postfix notation. 

BFS

Use a queue to implement this one.

Leave a Reply

Your email address will not be published. Required fields are marked *

     

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code class="" title="" data-url=""> <del datetime=""> <em> <i> <q cite=""> <strike> <strong> <pre class="" title="" data-url=""> <span class="" title="" data-url="">