Binary Trees
A tree data structure is a hierarchical structure that is used to represent and organize data in a way that is easy to navigate and search. It is a collection of nodes that are connected by edges and has a hierarchical relationship between the nodes.
The topmost node of the tree is called the root, and the nodes below it are called the child nodes. Each node can have multiple child nodes, and these child nodes can also have their own child nodes, forming a recursive structure.
A Tree Data Structure can be traversed in the following ways:
Depth First Search or DFS
Inorder Traversal
Preorder Traversal
Postorder Traversal
Level Order Traversal or Breadth First Search or BFS
Boundary Traversal
Diagonal Traversal
Inorder Traversal:
Algorithm Inorder(tree)
Traverse the left subtree, i.e., call function Inorder(left->subtree)
Visit the root.
Traverse the right subtree, i.e., call function Inorder(right->subtree)
Node takes in three arguments data, left and right. The root node is the initial node and every other child node derives from it.
Hence we need to create a node class and initialize a constructor by passing in the value and setting up the left and right values of a node to null.
The binary tree class is used to build the tree and it takes in a list of values and returns a new node of type node class.
The Inorder traversal is as follows :
Preorder Traversal:
Algorithm Preorder(tree)
Visit the root.
Traverse the left subtree, i.e., call Preorder(left->subtree)
Traverse the right subtree, i.e., call Preorder(right->subtree)
The function of the preorder places the root before the left and right subtree, the following code depicts the illustration.
Postorder Traversal:
Algorithm Postorder(tree)
Traverse the left subtree, i.e., call Postorder(left->subtree)
Traverse the right subtree, i.e., call Postorder(right->subtree)
Visit the root
The code for post-order traversal is as follows.
Thank you for today, If you liked this article please drop a like.