Data Structures: Key points about a Binary Tree – Part 1

I am fond of Data Structures and Algorithms. Most of the data listed below is from my notes that was captured during my study of Data Structures.

My major source of information on Data Structures is the book – ‘Data Structures Using C and C++ (2nd Edition) by Yedidyah Langsam, Moshe J. Augenstein, Aaron M. Tenenbaum’. You can find more information about the book in the References section at the end of this post.


Definition of a Binary Tree (Ref: Data Structures Using C and C++, 2nd Edition):

  • A Binary tree is a finite set of elements that are either empty or partitioned into three disjoint subsets.
  • The first subset contains a single element called ‘Root’ of the tree.
  • The other two subsets are themselves trees called ‘Left’ and ‘Right’ sub trees of the original tree.
  • A ‘left’ or ‘right’ sub tree can be empty.

Example of a Binary Tree:

Few key points about the tree listed in the example:

  • Each circle is termed as a ‘Node’.
  • Node labeled ‘A’ is called the ‘root’ Node.
  • Node labeled ‘A’ is also called the ‘father’ of Node labeled ‘B’ and Node labeled ‘C’.
  • Node labeled ‘B’ is termed as the ‘left son’ of Node labeled ‘A’.
  • Node labeled ‘C’ is the right son of Node labeled ‘A’.
  • Node ‘C’, ‘D’ and ‘E’ are called ‘leaf’ nodes since they have no children.
  • Node ‘B’ and ‘C’ are brothers.
  • Node ‘D’ and ‘E’ are the left descendants of ‘A’.
  • Node ‘A’ is the ancestor of ‘D’ and ‘E’.
  • Node ‘C’ can also be termed as the ‘right descendent’ of ‘A’.


Strictly Binary Tree:

  • Every non-leaf node in a binary tree has non-empty left and right sub trees.
  • A strictly binary tree with ‘n’ leaves has ‘2n-1’ nodes.

Example of a Strictly Binary Tree:


Level of a node in the binary tree:

  • The root of a tree has level 0 and the level of any other node in the tree is one more than the level of its father.

Depth of a binary tree:

  • The depth of a tree is the maximum level of any leaf in the tree.
  • This equals the length of the longest path from the ‘root’ node to any ‘leaf’ node.

Example of level and depth of a binary tree:

<hr /><strong>More Information:</strong>    <p>Part 2 of this article sheds light on ‘Complete Binary Trees’:</p>  <p><a href="https://ksearch.wordpress.com/2011/07/27/key-points-binary-tree-part-2/">https://ksearch.wordpress.com/2011/07/27/key-points-binary-tree-part-2/</a></p>  <hr />  <p><strong>Reference:</strong></p>  <ul>   <li><strong>Book: </strong>      <ul>       <li>Data Structures Using C and C++ (2nd Edition) by Yedidyah Langsam, Moshe J. Augenstein, Aaron M. Tenenbaum. Link to the book at Amazon: <a title="http://www.amazon.com/Data-Structures-Using-Yedidyah-Langsam/dp/0130369977" href="http://www.amazon.com/Data-Structures-Using-Yedidyah-Langsam/dp/0130369977">http://www.amazon.com/Data-Structures-Using-Yedidyah-Langsam/dp/0130369977</a> </li>     </ul>   </li> </ul>
Advertisements

One thought on “Data Structures: Key points about a Binary Tree – Part 1

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s