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
- Traverse all nodes of the left subtree (inorder).
- Visit the node itself.
- 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
- Visit the node itself.
- Traverse all nodes of the left subtree (preorder).
- 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
- Traverse all nodes of the left subtree (postorder).
- Traverse all nodes of the right subtree (postorder).
- 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]
Top comments (1)
Congratulations to your first article on DEV!