Tree definition and traversal

What is tree data structure?

The tree is a type of data structure that represents data hierarchically. Trees are a collection of nodes with a root node, and every node is connected to its parent node using edges. Every node has only one parent in a tree but can have multiple child nodes. The types of trees are as follows :

  1. General tree: The tree with no restriction of the number of child nodes is known as the general tree.
  2. Binary tree: A binary tree is a tree in which a node can have at most two nodes.

Traversal in tree and its types

Traversal is a way to visit each node in a tree. There are three main types of traversal in the tree data structure.

  1. In-order traversal: The pointer visits each node in non-decreasing order in the in-order traversal method.

    2. Algorithm

    1. Traverse to left subtree.
    2. Visit the root node.
    3. Traverse to right subtree.
  2. Pre-order traversal: Pre Order method creates a copy of the tree which it is traversing.

    3. Algorithm

    1. Visit the root node.
    2. Traverse to left subtree.
    3. Traverse to right subtree.
  3. Post-order traversal: Post-order is to delete the tree while traversing.

    4. Algorithm

    1. Traverse to left subtree.
    2. Traverse to right subtree.
    3. Visit the root node.