Priority Queues Top Binary Search Trees Contents

Binary Trees


A binary tree is a two-dimensional linked-list. Typically, a node in a binary tree has two next pointers, named left and right, and a value pointer. Binary tree nodes may have parent pointers, as well


    class binaryTreeNdde
        var value;
        var left;
        var right;

    class binaryTree
        var root;              //points to the root binary node


The terms used in describing a binary tree are:

Each node in the tree has either two children or no children.
A full tree with all the leaves at the same level.
A tree that is perfect except for, perhaps, the level furthest from the root. In that furthest level, all the leaves are piled up to the left. A heap is an example of a complete binary tree.
A tree is balanced if the longest path from the root to a leaf is not much longer than the shortest path. In other words, a nearly perfect tree. What constitutes "not much more" and "nearly" depends on the situation.
completely unbalanced
A tree is completely unbalanced if it has but one leaf.
The root node of a binary tree is the only node with no parent. It is considered the "top" of the tree, since trees are commonly drawn upside down, with the branches pointing downwards.
A node whose left and right pointers are null. In other words, a node with no children.
Other than the root, each node n has exactly one other node p pointing to it. The node p is said to be the parent of n.
Other than the leaves, each node p points to one or two other nodes. These nodes are said to be the children of p.
The other child of a parent node (if it exists).


Complete binary trees (heaps) are used in heapsorting and other higher-order algorithms.

The most common use of a binary tree is when it is formulated as a binary search tree.


Binary trees are implemented with nodes.


The common operations on a binary tree are insert, find, and delete. The actual implementation of these operations depends on the kind of binary tree, say a binary search tree or a heap.



In an in-order traversal is easily implemented using a recursive process that implements the following steps:

  1. traverse the left side
  2. process the node
  3. traverse the middle side

Note that the node processing step occurs "in the middle". Hence the name, in-order. Processing the node is a phrase meant to capture the purpose of the traversal. For printing out the nodes of a tree, processing the node means printing the value of the node. Here is such a traversal:

    function print-in-order(node)
        if (node.get-left() == null)


        if (node.get-right() == null)

This code can be simplified by the strategy of "falling off the tree". One detects a falling off by seeing if the given node has become null. If so, no processing is done. Recall that the null value is used to signify that a node pointer does not point to any node.

    function print-in-order(node)
        if (node != null)


A pre-order traversal is like an in-order traversal, except node processing happens first:

  1. process the node
  2. traverse the left side
  3. traverse the right side


In a post-order traversal, node processing happens last.


A level order uses a queue as an auxilliary structure. The traversal starts be enqueuing the root node. Next a loop:

The loop continues until the queue is empty.

Concept Inventory

  1. This is a question.
    1. This is one possible answer
    2. This is another possible answer

Priority Queues Top Binary Search Trees Contents