DEV Community

Captain Mcwiise
Captain Mcwiise

Posted on • Edited on

3

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.

Simple Tree

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.

Key Concepts Binary Tree

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. }
Enter fullscreen mode Exit fullscreen mode

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);
  }
}
Enter fullscreen mode Exit fullscreen mode

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);
  }
}
Enter fullscreen mode Exit fullscreen mode

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);
  }
}
Enter fullscreen mode Exit fullscreen mode

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

Top comments (1)

Collapse
 
szabgab profile image
Gabor Szabo

Congratulations to your first article on DEV!

Image of Docusign

🛠️ Bring your solution into Docusign. Reach over 1.6M customers.

Docusign is now extensible. Overcome challenges with disconnected products and inaccessible data by bringing your solutions into Docusign and publishing to 1.6M customers in the App Center.

Learn more