Tree in Data Structure: Definition, Types, and Traversing

Last Updated on January 16, 2023 by Prepbytes

In this article, we will discuss the tree data structure. We will discuss what a tree data structure is, what are its different types, and different tree traversals. So, let’s get started with the discussion.

Define Tree in Data Structure?

A Tree definition in data structure is a tree is a hierarchical data structure. It consists of multiple nodes that contain the actual data. The node that is at the top of the hierarchy is called the root node of a tree as shown below.

The node from which the next level nodes emerge is called the parent of those nodes and the nodes that emerge from the node on the previous level are called its children or child nodes.

A node in a tree might have 0 or more children. The nodes that do not have any children are called leaf nodes.

The leaf nodes are not necessarily the nodes on the last level. They are just nodes with 0 children. This is shown below.

A tree data structure is a hierarchical data structure used to fasten up the searching process because the N data nodes are not arranged linearly but rather in some different manner. The time taken to search for a value in the tree is said to be of the order of the height of the tree. Since the maximum height of a tree can be O(N), the worst-case complexity of searching remains the same in a tree i.e. O(N).

However, if it is linear, what’s the point of making a tree? That is exactly what we want to convey that trees are mostly non-linear only.

Let us now discuss different types of trees in detail.

Types of Trees in Data Structure

We can have different types of trees in data structure. Some main types are as follows.

Generic Tree

A generic tree is a tree data structure in which there is no limit to the number of child nodes each node can have. So, a node might have 2 children while some others might have 10 or 100 or any other number. An example generic tree data structure is shown below.

The node structure of a generic tree contains a list of child nodes for the current node as the number of children for any node is not fixed.

A generic tree is also called an N-ary tree. Let us now understand the next types of trees in data structure.

A generic tree Node is shown below.

Binary Tree

A binary tree is a tree in which a node can have a maximum of 2 children. So, the child nodes are named left and right children respectively. This is shown below.

So, the node structure of a binary tree will contain 2 node pointers viz, the left child and the right child.

The node structure for a binary tree is shown below.

Let us now look at Binary Search Trees.

Binary Search Tree

First of all, a binary search tree (BST) is a binary tree. Since it is a binary tree, it will have a maximum of 2 children per node. A binary search tree has one special property. All the values in the left subtree of a node will be smaller than the value in that node and all the values in the right subtree of any node will be greater than the value inside that node. An example binary tree is shown below.

So, we can see that the values in the left subtree of the root node are smaller than 10 and the values in the right subtree of the root node are greater than 10. This is not just true for the root node but for every node.

The node structure of a binary tree and BST is exactly the same as a BST is also a binary tree only.

Let us now study tree traversals.

Tree Traversal in Data Structure.

There are different methods by which we can traverse trees. Although the methods remain the same for any tree, we are going to discuss the methods using a binary tree in this discussion. So, let’s get started.

Consider the tree given below.

Right now, we are at the tree’s root node. According to the preorder traversal, we must follow the "root left right" sequence. This implies that we must label a node as visited as soon as we arrive at it.

The images above show that as soon as we reach a node in our traversal, consider it visited. So, the complete preorder traversal is shown below.

The order of the inorder traversal is "left root right." This indicates that we traverse the left subtree first completely, traverse the right subtree next, and then mark the present node as visited. This is seen below.

Since we kept going to the left node, we have not recorded any nodes as visited along the way. No left node is present for node 4 at this time. We can therefore state that we have travelled through its left node. Now that the order is "left node right," we must mark the node visited after visiting the left node. As a result, node 4 is marked as visited.

Similarly, the entire tree is traversed.

The postorder traversal now follows the "left right root" order. This indicates that we must first completely tour the left subtree, then completely traverse the right subtree, and last, we must mark the node visited.

We have not yet visited any nodes because we continued going to the left node of each node as we moved forward. We can now observe that Node 4 has no left node. We can therefore claim to have visited the left node. There is no right node either. We can therefore claim to have also visited the right node. We may now mark the currently visited node. In the postorder traversal, Node 4 is the first node.

We keep on moving further as shown below.

At Node 8, we don’t have any left or right nodes. Hence, we can say that we have visited the left and right nodes of Node 8. So, mark it visited as well.

We now return to node 5. Here, we can see that we’ve been to the left subtree of the node 5. Node 5 has no right child. We can therefore claim to have visited both of the children. We should therefore also include 5 in the postorder traversal.

When we are at Node 2, we have already visited the left subtree (Node 4) and the right subtree (starting from Node 5) as well. So, we can now mark Node 2 as visited.

Similarly, you can complete the rest of the traversal as well. The complete postorder traversal of the tree is shown below.

So, for a better understanding, have a look at the image shown below.

Pre-node regions are whenever we are to the left of any node, meaning that no child has yet been explored. We are in the in-node area whenever we are halfway between a node’s left and right children, that is when the left subtree has been traversed but the right subtree has not. Similar to this, we are in the post-node region whenever we are to the right of a node, meaning both of its children have been traversed.

So, the program for preorder, postorder, and inorder traversals of a binary tree is shown below.

Java Program for Tree Traversal in Data Structure

class Node {
    int key;
    Node left, right;

    public Node(int item)
    {
        key = item;
        left = right = null;
    }
}

class BinaryTree {
    Node root;

    BinaryTree() { root = null; }

     void printPreorder(Node node)
    {
        if (node == null)
            return;
 
        System.out.print(node.key + " ");
        printPreorder(node.left);
        printPreorder(node.right);
    }
 
    void printPreorder() { printPreorder(root); }
    
    void printInorder(Node node)
    {
        if (node == null)
            return;

        printInorder(node.left);
        System.out.print(node.key + " ");
        printInorder(node.right);
    }
    
    void printInorder() { printInorder(root); }
    
     void printPostorder(Node node)
    {
        if (node == null)
            return;
 
        printPostorder(node.left);
        printPostorder(node.right);
        System.out.print(node.key + " ");
    }
 
    void printPostorder() { printPostorder(root); }

    public static void main(String[] args)
    {
        BinaryTree tree = new BinaryTree();
        tree.root = new Node(1);
        tree.root.left = new Node(2);
        tree.root.right = new Node(3);
        tree.root.left.left = new Node(4);
        tree.root.left.right = new Node(5);

        
        System.out.println("Preorder traversal of binary tree is ");
        tree.printPreorder();
        
        System.out.println("\nInorder traversal of binary tree is ");
        tree.printInorder();
        
        System.out.println("\nPostorder traversal of binary tree is ");
        tree.printPostorder();
    }
}

Conclusion
So, we have seen the definition, types of trees, and traversals of trees in this article. We hope that you liked the discussion and understood the concepts well. We hope to see you again soon at PrepBytes.

Let us now look at some Frequently Asked Questions (FAQs)

FAQs

1. Give one application of the tree data structure.
The tree data structure is used for faster searching. It is used for implementing B-Tree indexing in RDBMS for implementing the Index Seek storage method that allows faster search of data when a query is run.

2. Why is the node of the tree data structure called self-referential?
Self-referential means referring to itself. No, the tree node does not have a pointer to itself. However, when a tree node structure or class is made, it contains either a list of Nodes or left and right nodes. Basically, we make the class Node and the data members are also of the type nodes. So, it seems that the node points to other nodes and that is in fact the case in a tree. Thus, a tree node class or structure is called self-referential.

3. What is the Time Complexity of Tree Traversal in BST?
Whether it is BST or any other tree, tree traversal refers to traversing the entire tree. This means that we should cover all the N nodes in a tree traversal. Thus, the time complexity of tree traversal is O(N).