Introduction to Binary Trees

Basic Definitions

• Binary Tree
  A binary tree is made of a set of nodes. This set can be empty or it can consist of a node called a root along with two disjoint subtrees.
• Disjoint subtrees
  Trees that have no nodes in common.
• Node
  A node contains a value and links to two (binary) other nodes called children (left and right). These links are called edges. A node also might link to its parent node.
• Descendant node
  Nodes of any subtree are descendants of its root.
• Ancestor node
  A root of a subtree is an ancestor of it’s nodes.
• Path from n₁ to n_k
  The path from n1 to nk is the sequence of nodes n1, n2 ... nk. Where each node ni in the sequence is a parent of node ni + 1 (each node is a parent of the next / going from the top downwards).
• Depth/Level of node M
  The length of the path between the root of the tree R and M. The root node R is at level 0.
• Height of a tree
  More than the depth of the deepest node in the tree by one. height = max(depth) + 1.
• Leaf/External node
  A node that has no children. Has neither right nor left subtree.
  !hasLeft AND !hasRight = !(hasLeft OR hasRight)
• Internal node
  A node that has at least one child. Has a right or a left subtree. Or both. An internal node is the opposite of an external node.
  hasLeft OR hasRight = !(!hasLeft AND !hasRight)
• Full tree
  A binary tree which consists of nodes that must satisfy one of the following conditions:
  • An internal node with two non-empty children.
  • A leaf.

  Each node must have either 0 or 2 children. Uni-child nodes aren’t allowed.

• Complete tree
  A binary tree which in which all the levels are full except the last level. You can think of it as a tree that is filled from left to right level by level.
  You might confuse a complete tree with a full tree. A little mind trick to memorize them is: the word complete is wider than the word full, so is the complete tree — always wider than the full tree–.

Full Binary Theorem

• The number of leaves in a non-empty full binary tree = number of internal nodes + 1
• The number of empty subtrees in a non-empty binary tree = number of nodes in the tree + 1

Proven by mathematical induction.

Traversal

A tree’s nodes are placed in such structure for a reason. We want to process the tree’s nodes — one by one — by visiting them in a certain order.
These ways/orders by which we visit the nodes are called traversals. A traversal on a tree generates a sequence of nodes in which each node appears once and only once. This is called an enumeration.
There are three types of traversal: pre-order, post-order and in-order. They’ll be explained using the following figure.

Imagine you’re starting from the root of the tree and draw a border around the tree parallel to the edges and surrounding each branch as shown.
Whenever you pass through the left of a node, you’re in pre-order. When you are below a node, you’re in in-order. If you are to the right of a node, you’re in post-order.

• Pre-Order

The algorithm goes as follows:

preoreder(node)
	if(node == null)
		return;
	do(node)
	preorder(node.left)
	preorder(node.right)

• In-Order

The algorithm goes as follows:

inoreder(node)
	if(node == null)
		return;
	inorder(node.left)
	do(node)
	inorder(node.right)

• Post-Order

The algorithm goes as follows:

postoreder(node)
	if(node == null)
		return;
	postorder(node.left)
	postorder(node.right)
	do(node)

You can do these traversals simultaneously in a more general manner instead of only one at a time by gluing them together. The procedure should looks like this:

traverse(node)
	if(node == null)
		return;
	doPreOrder(node)
	traverse(node.left)
	doInOrder(node)
	traverse(node.right)
	doPostOrder(node)