(all the photos used are from google btw)
Its been a while, I hope you all are doing well.
In this post, I wanted to share some basic knowledge of trees in programming and data structures.
We are starting with the trees. A tree is a data structure used to simulate a hierarchical tree structure. A node of the tree has a root value and a list of references to other nodes which are referred to as child nodes.
The most typical tree structure used is the Binary tree. As the name suggests, each node of the binary tree has at most two children referred to as left child and right child.
Notice the image above to understand a visual representation of how this looks like.
Def. of Traverse ~ travel across or through.
--Pre-order traversal is to visit the root first. Then traverse the left subtree. Finally, traverse the right subtree.
The red indicates that we return from the visit on the node to move to the next node, but continue to move down on all left nodes.
--In-order traversal is to traverse the left subtree first. Then visit the root. Finally, traverse the right subtree
In a binary search tree, all data is retrieved in a sorted order using in-order traversal.
--Traverse the left subtree first. Then traverse the right subtree. Finally, visit the root.
I hope this makes sense and simplified the Binary Tree. Next post I'd like to cover recursions using one of these traverse methods.
When you delete nodes in a tree, deletion process will be in post-order, when you delete a node, you will delete its left child and its right child before you delete the node itself.