Computer Science Wiki

Search

SearchSearch

ADT - Binary Tree

Sep 13, 20243 min read

Abstract data type:

Implementation:

Data_StructureTreeBinary_TreeComplete_Binary_TreeArray_Represented_Binary_Tree

A binary tree is an ordered tree that each node can have at most two children, referred to as the left child and the right child. Child ordering is left followed by right. A binary tree is proper when every node has 0 or 2 children.

graph TD;
id1((A)) --> id2((B));
id1((A)) --> id3((C));
id2((B)) --> id4((D));
id2((B)) --> id5((E));
id3((C)) --> id7((F));
id5((E)) --> id6((G));

Operations

A binary tree extends the tree operations, inherits all the methods of a tree. Additional methods:

  • position leftChild(p)
  • position rightChild(p)
  • position sibling(p)

Complete binary tree

A complete binary tree is a where all level of the binary tree are filled except possible for the last level, and the last level is filled from left to right.

In this example, it is not a complete binary tree as in level 2 (the root level is level 0), the C is missing a right child to make this tree a complete binary tree.

graph TD;
id1((A)) --> id2((B));
id1((A)) --> id3((C));
id2((B)) --> id4((D));
id2((B)) --> id5((E));
id3((C)) --> id7((F));
id5((E)) --> id6((H));
id4((D)) --> id8((I));
id4((D)) --> id9((H));

The following tree is a complete binary tree, although the last level is not filled full, it its filled from the left to right, and still preserve the complete binary tree property.

graph TD;
id1((A)) --> id2((B));
id1((A)) --> id3((C));
id2((B)) --> id4((D));
id2((B)) --> id5((E));
id3((C)) --> id7((F));
id3((C)) --> id6((G));
id4((D)) --> id8((H));

Representation

A binary tree can be represented with sequential representation (normally array) and linked representation (normally linked list)

Sequential representation

Using array to represent binary tree is most commonly done with a complete binary tree due to its compact nature and its efficient use of space. When considering index,

  • If a node is at index i
  • Its left child is at 2i + 1
  • Its right child is at 2i + 2
  • its parent is at (i-1) / 2

Consider the below example:

graph TD;
id1((A)) --> id2((B));
id1((A)) --> id3((C));
id2((B)) --> id4((D));
id2((B)) --> id5((E));
id3((C)) --> id7((F));
id3((C)) --> id6((G));
id4((D)) --> id8((H));

We can represent this binary tree in array:

{A, B, C, D, E, F, G ,H}

We want to find the left and right child of node C, we know that C is at index 2.

  • Left child at index: , which is F
  • Right child at index , which if G
  • To backtrace and find their parent
    • Using left child which is at index 5,
    • Using right child which is at index 6, (this is an integer division)

When using array to represent incomplete binary trees, you may end up with some unused spaces in the array.

Back to parent page: Data Structures and Algorithms

Graph View

Backlinks