DEV Community


Posted on

Data Structure: Binary Tree

Hello All!
(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.

Image description

Notice the image above to understand a visual representation of how this looks like.

Traversal Methods used in a Binary Tree

Def. of Traverse ~ travel across or through.

Pre-order Traversal
--Pre-order traversal is to visit the root first. Then traverse the left subtree. Finally, traverse the right subtree.
Image description
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
--In-order traversal is to traverse the left subtree first. Then visit the root. Finally, traverse the right subtree

Image description

In a binary search tree, all data is retrieved in a sorted order using in-order traversal.

Post-order Traversal
--Traverse the left subtree first. Then traverse the right subtree. Finally, visit the root.

Image description
Personally I think this one is a bit hard foe me to wrap my head around. Spend some time running the numbers back in your head and understand the map.

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.

Discussion (0)