Binary Tree

data structure checklist

One interesting aspect about binary trees is the way to store and represent them. Linked lists provide an intuitive illustration of binary trees, while extra spaces are required for pointers. Arrays seem to enable the most compact representation for binary trees, but the advantage only applies to some cases like complete binary trees.

Another interesting aspect about binary trees is the strategy of traversing all nodes of a binary tree, which is demonstrated in other articles (e.g., iterative traversal and Morris traversal ).

Storing based on linked lists

Linked lists provide an intuitive representation of binary trees. Under a linked list, every node of a binary tree stores three kinds of information: the value of the node, the pointer to the left child, and the pointer to the right child.

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

Storing based on arrays

Binary trees can also be stored in arrays. Given an array \(a\), we store the root node of a binary tree in \(a[1]\). Then recursively, for each existing node stored in \(a[i]\), we store its left and right children in \(a[2i]\) and \(a[2i+1]\) respectively. On the other hand, for each existing non-root node stored in \(a[j]\), its parent can be accessed in \(a[{j\over2}]\). Note that such approach would leave \(a[0]\) empty. Alternatively, we can also start from \(a[0]\) without wasting its space. Accordingly, for each node in \(a[k]\), its left and right children are located in \(a[2k+1]\) and \(a[2k+2]\) respectively, and its parent is in \(a[{k-1\over2}]\).

Compared to linked lists, which store both binary tree values and children pointers, arrays only store the former. However, this does not guarantee that arrays are always more space efficient over linked lists. Given a binary tree with many leaf nodes that are not in the last level of the tree, an array storing that binary tree tends to be sparse, whereas a linked list representing that binary tree has no spaces wasted since it’s allocated dynamically.

Complete binary tree

Arrays are able to achieve the most space efficiency when storing complete binary trees. In a complete binary tree, every level, except possibly the last, is completely filled, and all nodes in the last level are as far left as possible. Apparently there are no spaces wasted except the first slot (e.g., \(a[0]\), which is always blank). Given an array storing a complete binary tree with \(n\) nodes, the first half range (from \(a[1]\) to \(a[{n \over 2}]\)) represents non-leaf nodes while the rest (from \(a[{n \over 2} + 1]\) to \(a[n]\)) represents leaf nodes. Note that such space efficiency does not apply to full binary trees, in which every node has either zero or two children by definition.

Contents