Skip to content

DA4. Binary Trees

Statement

In your own words:

  • provide a definition of a binary tree and discuss its’ implementation.
  • Include in your discussion the following terminology: Root, Node, Sub-Tree, Height, Depth, and Leaf

Solution

  • The binary tree is a data structure that organizes a set of elements in a certain way that allows for efficient manipulation on those elements.
  • Each element in the tree is a Node that has a value and pointers to other nodes; -two at most- that are called children.
  • A Node that has no children is called a Leaf.
  • The first Node is a special one called the Root, that is the entry point to the tree.
  • For a Binary tree with a single node, this node is the Root and a Leaf at the same time.
  • A Node that has One or Two Children and a Parent is called an Internal Node.
  • Each Child Node (right, or left) is a Root, forming with its Children (if any) and it’s Children’s Children (if any) a Sub-Tree of the original tree, that goes down until it reaches its Leafs.
  • The Depth of a Node is the number of edges that needs to be followed (traversed, or visited) to reach from the Root to that Node.
  • The Root has a Depth of 0, and the Depth goes up as we go down the tree.
  • The Height of a Node is the number of edges that needs to be followed (traversed, or visited) to reach from that Node to its deepest Leaf. (The Height of a Leaf is 0).
  • The Height of the tree is the maximum Height of all the Nodes in the tree, which equals the Height from the deepest Leaf in the tree to the Root.
  • The Height of a tree with a single Node is 0. (The Root is the deepest Leaf).
  • The binary tree can be implemented based on an array, or a linked list.
  • The time complexity of both implementations is almost the same
  • The array implementation is more space efficient for a complete tree (the size is known in advance), and used implement Heaps (a special type of binary tree) and Sorting algorithms.
  • The linked list implementation is more space efficient for a sparse tree (the size is not known in advance), and used to implement Binary Search Trees (BSTs) and other types of trees.

References

  • Shaffer, C. (2011). A Practical Introduction to Data Structures and Algorithm Analysis. Blacksburg: Virginia. Tech. https://people.cs.vt.edu/shaffer/Book/JAVA3e20130328.pdf. Chapter 5.
  • Barnett, G. & Del Tongo, L. (2008). Data Structures and Algorithms: An Annotated Reference with Examples. Chapter 3: Binary Search Tree and Chapter 4: Heaps.