Binary Tree Data Structure Vol. 1

Source code of the examples on Github.

What is a Tree?

A tree is a non-linear data structure composed of nodes and edges without cycles. It means that every node in a tree has one and only one edge connecting two nodes:

• Node: it is an element that contains a particular information plus the addresses to downward nodes also called children.
• Edge: it just connects 2 nodes.

What is a Binary Tree?

A binary tree is the simplest type of a tree, where nodes can have from zero to 2 children at most.

Key Concepts

• Root: this is the node at the top of the tree.
• Path: refers to a sequence of nodes along with the edges.
• Parent: every node except for the root node has one edge connecting to an upward node, this one is called parent.
• Child: a node below another node connected by one edge is referred as child.
• Leaf: a node which does not have any children.
• Subtree: all descendants of a node below the root node.
• Level: number of edges between the root node and the deepest leaf.
• Value: the content of the node also referred as info.

A Brief Intro to Recursiveness

Traversing a binary tree is usually a recursive process, and I say usually because of there are other alternatives to implement traversing algorithms with stacks or queues. However, I consider is better to analyze binary trees from a recursive perspective for academic purposes.

Recursive Function

A recursive function is no more than a function which calls itself until a condition is meet. Have a look at the following example:

1.  public static void main(String[] args) {
2.    var r = Tales.sillySum(0);
3.    System.out.println(r);
4.  }
5.
6.  public static int sillySum(int acc){
7.    if(acc == 10){
8.      return acc;
9.    } else {
10.     acc++;
11.     return sillySum(acc);
12.   }
13. }

Where we can identify 2 key parts of a recursive function:

• halting condition: the condition that stops the recursive process (line 7), this is also called the base case.
• recursive statement: when the function is called itself (line 11).

Traversing a Binary Tree

Traversing means to pass through all nodes of a binary tree just one time in a specific order, therefore we can say that every node is a potential subtree to be traversed, even if it is a leaf.

Now, lets explore the 3 flavors we have to traverse the binary tree of the chart, and refer to visit as the action of printing out the value of a node, please keep in mind the 2 key concepts of a recursive function, so you can identify where the recursiveness happens:

Inorder traversal

1. Traverse all nodes of the left subtree (inorder).
2. Visit the node itself.
3. Traverse all nodes of the right subtree (inorder).

public void inOrderTraversal(Node parent) {
  if (parent == null){
    return;
  } else {
    inOrderTraversal(parent.left);
    System.out.print(parent.value);
    inOrderTraversal(parent.right);
  }
}

Outcome: [4,2,6,5,7,8,1,3]

Preorder traversal

1. Visit the node itself.
2. Traverse all nodes of the left subtree (preorder).
3. Traverse all nodes of the right subtree (preorder).

public void preOrderTraversal(Node parent) {
  if (parent == null){
    return;
  } else {
    System.out.print(parent.value);
    preOrderTraversal(parent.left);
    preOrderTraversal(parent.right);
  }
}

Outcome: [1,2,4,5,6,7,8,3]

Postorder traversal

1. Traverse all nodes of the left subtree (postorder).
2. Traverse all nodes of the right subtree (postorder).
3. Visit the node itself.

public void postOrderTraversal(Node parent) {
  if (parent == null){
    return;
  } else {
    postOrderTraversal(parent.left);
    postOrderTraversal(parent.right);
    System.out.print(parent.value);
  }
}

Outcome: [4,6,8,7,5,2,3,1]