{"id":11675,"date":"2023-01-16T07:54:12","date_gmt":"2023-01-16T07:54:12","guid":{"rendered":"https:\/\/www.prepbytes.com\/blog\/?p=11675"},"modified":"2023-01-16T07:54:12","modified_gmt":"2023-01-16T07:54:12","slug":"tree-in-data-structure-definition-types-and-traversing","status":"publish","type":"post","link":"https:\/\/prepbytes.com\/blog\/tree-in-data-structure-definition-types-and-traversing\/","title":{"rendered":"Tree in Data Structure: Definition, Types, and Traversing"},"content":{"rendered":"<p><img decoding=\"async\" src=\"https:\/\/prepbytes-misc-images.s3.ap-south-1.amazonaws.com\/assets\/1673853546595-Tree%20in%20Data%20Structure.jpg\" alt=\"\" \/><\/p>\n<p>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\u2019s get started with the discussion.<\/p>\n<h2>Define Tree in Data Structure?<\/h2>\n<p>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.<\/p>\n<p><img decoding=\"async\" src=\"https:\/\/prepbytes-misc-images.s3.ap-south-1.amazonaws.com\/assets\/1673853546908-Tree%20in%20Data%20Structure1.png\" alt=\"\" \/><\/p>\n<p>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.<\/p>\n<p><img decoding=\"async\" src=\"https:\/\/prepbytes-misc-images.s3.ap-south-1.amazonaws.com\/assets\/1673853546916-Tree%20in%20Data%20Structure2.png\" alt=\"\" \/><\/p>\n<p>A node in a tree might have 0 or more children. The nodes that do not have any children are called leaf nodes. <\/p>\n<p><img decoding=\"async\" src=\"https:\/\/prepbytes-misc-images.s3.ap-south-1.amazonaws.com\/assets\/1673853546916-Tree%20in%20Data%20Structure3.png\" alt=\"\" \/><\/p>\n<p>The leaf nodes are not necessarily the nodes on the last level. They are just nodes with 0 children. This is shown below.<\/p>\n<p><img decoding=\"async\" src=\"https:\/\/prepbytes-misc-images.s3.ap-south-1.amazonaws.com\/assets\/1673853546981-Tree%20in%20Data%20Structure4.png\" alt=\"\" \/><\/p>\n<p>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).<\/p>\n<p>However, if it is linear, what\u2019s the point of making a tree? That is exactly what we want to convey that trees are mostly non-linear only.<\/p>\n<p>Let us now discuss different types of trees in detail.<\/p>\n<h2>Types of Trees in Data Structure<\/h2>\n<p>We can have different types of trees in data structure. Some main types are as follows.<\/p>\n<h3>Generic Tree<\/h3>\n<p>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.<\/p>\n<p><img decoding=\"async\" src=\"https:\/\/prepbytes-misc-images.s3.ap-south-1.amazonaws.com\/assets\/1673853546984-Tree%20in%20Data%20Structure5.png\" alt=\"\" \/><\/p>\n<p>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.<\/p>\n<p>A generic tree is also called an N-ary tree. Let us now understand the next types of trees in data structure.<\/p>\n<p>A generic tree Node is shown below.<\/p>\n<p><img decoding=\"async\" src=\"https:\/\/prepbytes-misc-images.s3.ap-south-1.amazonaws.com\/assets\/1673853546986-Tree%20in%20Data%20Structure6.png\" alt=\"\" \/><\/p>\n<h3>Binary Tree<\/h3>\n<p>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.<\/p>\n<p><img decoding=\"async\" src=\"https:\/\/prepbytes-misc-images.s3.ap-south-1.amazonaws.com\/assets\/1673853546987-Tree%20in%20Data%20Structure7.png\" alt=\"\" \/><\/p>\n<p>So, the node structure of a binary tree will contain 2 node pointers viz, the left child and the right child. <\/p>\n<p>The node structure for a binary tree is shown below.<\/p>\n<p><img decoding=\"async\" src=\"https:\/\/prepbytes-misc-images.s3.ap-south-1.amazonaws.com\/assets\/1673853546987-Tree%20in%20Data%20Structure8.png\" alt=\"\" \/><\/p>\n<p>Let us now look at Binary Search Trees.<\/p>\n<h3>Binary Search Tree<\/h3>\n<p>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.<\/p>\n<p><img decoding=\"async\" src=\"https:\/\/prepbytes-misc-images.s3.ap-south-1.amazonaws.com\/assets\/1673853546994-Tree%20in%20Data%20Structure9.png\" alt=\"\" \/><\/p>\n<p>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.<\/p>\n<p>The node structure of a binary tree and BST is exactly the same as a BST is also a binary tree only.<\/p>\n<p>Let us now study tree traversals.<\/p>\n<h3>Tree Traversal in Data Structure.<\/h3>\n<p>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\u2019s get started.<\/p>\n<p>Consider the tree given below.<\/p>\n<p><img decoding=\"async\" src=\"https:\/\/prepbytes-misc-images.s3.ap-south-1.amazonaws.com\/assets\/1673853546994-Tree%20in%20Data%20Structure10.png\" alt=\"\" \/><\/p>\n<p>Right now, we are at the tree&#8217;s root node.  According to the <strong>preorder<\/strong> traversal, we must follow the <strong>&quot;root left right&quot;<\/strong> sequence. This implies that we must label a node as visited as soon as we arrive at it.<\/p>\n<p><img decoding=\"async\" src=\"https:\/\/prepbytes-misc-images.s3.ap-south-1.amazonaws.com\/assets\/1673853546994-Tree%20in%20Data%20Structure11.png\" alt=\"\" \/><\/p>\n<p><img decoding=\"async\" src=\"https:\/\/prepbytes-misc-images.s3.ap-south-1.amazonaws.com\/assets\/1673853546994-Tree%20in%20Data%20Structure12.png\" alt=\"\" \/><\/p>\n<p><img decoding=\"async\" src=\"https:\/\/prepbytes-misc-images.s3.ap-south-1.amazonaws.com\/assets\/1673853547005-Tree%20in%20Data%20Structure13.png\" alt=\"\" \/><\/p>\n<p>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.<\/p>\n<p><img decoding=\"async\" src=\"https:\/\/prepbytes-misc-images.s3.ap-south-1.amazonaws.com\/assets\/1673853547005-Tree%20in%20Data%20Structure14.png\" alt=\"\" \/><\/p>\n<p>The order of the <strong>inorder<\/strong> traversal is <strong>&quot;left root right.&quot;<\/strong> 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.<\/p>\n<p><img decoding=\"async\" src=\"https:\/\/prepbytes-misc-images.s3.ap-south-1.amazonaws.com\/assets\/1673853547005-Tree%20in%20Data%20Structure15.png\" alt=\"\" \/><\/p>\n<p>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 &quot;left node right,&quot; we must mark the node visited after visiting the left node. As a result, node 4 is marked as visited.<\/p>\n<p><img decoding=\"async\" src=\"https:\/\/prepbytes-misc-images.s3.ap-south-1.amazonaws.com\/assets\/1673853547006-Tree%20in%20Data%20Structure16.png\" alt=\"\" \/><\/p>\n<p>Similarly, the entire tree is traversed.<\/p>\n<p><img decoding=\"async\" src=\"https:\/\/prepbytes-misc-images.s3.ap-south-1.amazonaws.com\/assets\/1673853547006-Tree%20in%20Data%20Structure17.png\" alt=\"\" \/><\/p>\n<p>The <strong>postorder<\/strong> traversal now follows the <strong>&quot;left right root&quot;<\/strong> 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.<\/p>\n<p><img decoding=\"async\" src=\"https:\/\/prepbytes-misc-images.s3.ap-south-1.amazonaws.com\/assets\/1673853547017-Tree%20in%20Data%20Structure18.png\" alt=\"\" \/><\/p>\n<p>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.<\/p>\n<p><img decoding=\"async\" src=\"https:\/\/prepbytes-misc-images.s3.ap-south-1.amazonaws.com\/assets\/1673853547017-Tree%20in%20Data%20Structure19.png\" alt=\"\" \/><\/p>\n<p>We keep on moving further as shown below.<\/p>\n<p><img decoding=\"async\" src=\"https:\/\/prepbytes-misc-images.s3.ap-south-1.amazonaws.com\/assets\/1673853547017-Tree%20in%20Data%20Structure19.png\" alt=\"\" \/><\/p>\n<p>At Node 8, we don\u2019t 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.<\/p>\n<p><img decoding=\"async\" src=\"https:\/\/prepbytes-misc-images.s3.ap-south-1.amazonaws.com\/assets\/1673853547017-Tree%20in%20Data%20Structure20.png\" alt=\"\" \/><\/p>\n<p>We now return to node 5. Here, we can see that we&#8217;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.<\/p>\n<p><img decoding=\"async\" src=\"https:\/\/prepbytes-misc-images.s3.ap-south-1.amazonaws.com\/assets\/1673853547037-Tree%20in%20Data%20Structure21.png\" alt=\"\" \/><\/p>\n<p>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.<\/p>\n<p><img decoding=\"async\" src=\"https:\/\/prepbytes-misc-images.s3.ap-south-1.amazonaws.com\/assets\/1673853547037-Tree%20in%20Data%20Structure22.png\" alt=\"\" \/><\/p>\n<p>Similarly, you can complete the rest of the traversal as well. The complete postorder traversal of the tree is shown below.<\/p>\n<p><img decoding=\"async\" src=\"https:\/\/prepbytes-misc-images.s3.ap-south-1.amazonaws.com\/assets\/1673853547041-Tree%20in%20Data%20Structure23.png\" alt=\"\" \/><\/p>\n<p>So, for a better understanding, have a look at the image shown below.<\/p>\n<p><img decoding=\"async\" src=\"https:\/\/prepbytes-misc-images.s3.ap-south-1.amazonaws.com\/assets\/1673853547057-Tree%20in%20Data%20Structure24.png\" alt=\"\" \/><\/p>\n<p>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&#8217;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.<\/p>\n<p>So, the program for preorder, postorder, and inorder traversals of a binary tree is shown below.<\/p>\n<h2>Java Program for Tree Traversal in Data Structure<\/h2>\n\t\t\t\t\t\t<style>\r\n\t\t\t\t\r\n\t\t\t\t\t#tab_container_11622 {\r\n\toverflow:hidden;\r\n\tdisplay:block;\r\n\twidth:100%;\r\n\tborder:0px solid #ddd;\r\n\tmargin-bottom:30px;\r\n\t}\r\n\r\n#tab_container_11622 .tab-content{\r\n\tpadding:20px;\r\n\tborder: 1px solid #e6e6e6 !important;\r\n\tmargin-top: 0px;\r\n\tbackground-color:#ffffff !important;\r\n\tcolor: #000000 !important;\r\n\tfont-size:16px !important;\r\n\tfont-family: Open Sans !important;\r\n\t\r\n\t\tborder: 1px solid #e6e6e6 !important;\r\n\t}\r\n#tab_container_11622 .wpsm_nav-tabs {\r\n    border-bottom: 0px solid #ddd;\r\n}\r\n#tab_container_11622 .wpsm_nav-tabs > li.active > a, #tab_container_11622 .wpsm_nav-tabs > li.active > a:hover, #tab_container_11622 .wpsm_nav-tabs > li.active > a:focus {\r\n\tcolor: #000000 !important;\r\n\tcursor: default;\r\n\tbackground-color: #ffffff !important;\r\n\tborder: 1px solid #e6e6e6 !important;\r\n}\r\n\r\n#tab_container_11622 .wpsm_nav-tabs > li > a {\r\n    margin-right: 0px !important; \r\n    line-height: 1.42857143 !important;\r\n    border: 1px solid #d5d5d5 !important;\r\n    border-radius: 0px 0px 0 0 !important; \r\n\tbackground-color: #e8e8e8 !important;\r\n\tcolor: #000000 !important;\r\n\tpadding: 15px 18px 15px 18px !important;\r\n\ttext-decoration: none !important;\r\n\tfont-size: 14px !important;\r\n\ttext-align:center !important;\r\n\tfont-family: Open Sans !important;\r\n}\r\n#tab_container_11622 .wpsm_nav-tabs > li > a:focus {\r\noutline: 0px !important;\r\n}\r\n\r\n#tab_container_11622 .wpsm_nav-tabs > li > a:before {\r\n\tdisplay:none !important;\r\n}\r\n#tab_container_11622 .wpsm_nav-tabs > li > a:after {\r\n\tdisplay:none !important ;\r\n}\r\n#tab_container_11622 .wpsm_nav-tabs > li{\r\npadding:0px !important ;\r\nmargin:0px;\r\n}\r\n\r\n#tab_container_11622 .wpsm_nav-tabs > li > a:hover , #tab_container_11622 .wpsm_nav-tabs > li > a:focus {\r\n    color: #000000 !important;\r\n    background-color: #e8e8e8 !important;\r\n\tborder: 1px solid #d5d5d5 !important;\r\n\t\r\n}\r\n#tab_container_11622 .wpsm_nav-tabs > li > a .fa{\r\n\r\nmargin-right:5px !important;\r\n\r\nmargin-left:5px !important;\r\n\r\n\r\n}\r\n\r\n\t\t#tab_container_11622 .wpsm_nav-tabs a{\r\n\t\t\tbackground-image: none;\r\n\t\t\tbackground-position: 0 0;\r\n\t\t\tbackground-repeat: repeat-x;\r\n\t\t}\r\n\t\t\t\r\n\r\n\r\n#tab_container_11622 .wpsm_nav-tabs > li {\r\n    float: left;\r\n    margin-bottom: -1px !important;\r\n\tmargin-right:0px !important; \r\n}\r\n\r\n\r\n#tab_container_11622 .tab-content{\r\noverflow:hidden !important;\r\n}\r\n\r\n\r\n@media (min-width: 769px) {\r\n\r\n\t#tab_container_11622 .wpsm_nav-tabs > li{\r\n\t\tfloat:left !important ;\r\n\t\t\t\tmargin-right:-1px !important;\r\n\t\t\t\t\t}\r\n\t#tab_container_11622 .wpsm_nav-tabs{\r\n\t\tfloat:none !important;\r\n\t\tmargin:0px !important;\r\n\t}\r\n\r\n\t#tab_container_11622 .wpsm_nav-tabs > li {\r\n\t\t\t\t\r\n\t}\r\n\t#tab_container_11622 .wpsm_nav{\r\n\t\t\t}\r\n\r\n}\r\n\r\n\r\n\r\n@media (max-width: 768px) {\r\n\t#tab_container_11622 .wpsm_nav-tabs > li {\r\n\t\t\t\t\r\n\t}\r\n\t#tab_container_11622 .wpsm_nav{\r\n\t\t\t}\r\n}\r\n\r\n\r\n\t.wpsm_nav-tabs li:before{\r\n\t\tdisplay:none !important;\r\n\t}\r\n\r\n\t@media (max-width: 768px) {\r\n\t\t\t\t\r\n\t\t\t\t.wpsm_nav-tabs{\r\n\t\t\tmargin-left:0px !important;\r\n\t\t\tmargin-right:0px !important; \r\n\t\t\t\r\n\t\t}\r\n\t\t\t\t#tab_container_11622 .wpsm_nav-tabs > li{\r\n\t\t\tfloat:none !important;\r\n\t\t}\r\n\t\t\t\r\n\t}\t\t\t\t<\/style>\r\n\t\t\t\t<div id=\"tab_container_11622\" >\r\n\t \r\n\t\t\t\t\t<ul class=\"wpsm_nav wpsm_nav-tabs\" role=\"tablist\" id=\"myTab_11622\">\r\n\t\t\t\t\t\t\t\r\n\t\t\t\t\t\t\t<li role=\"presentation\"  class=\"active\"  onclick=\"do_resize()\">\r\n\t\t\t\t\t\t\t\t<a href=\"#tabs_desc_11622_1\" aria-controls=\"tabs_desc_11622_1\" role=\"tab\" data-toggle=\"tab\">\r\n\t\t\t\t\t\t\t\t\t\r\n\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t<i class=\"fa fa-code\"><\/i> \t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\r\n\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\r\n\t\t\t\t\t\t\t\t\t<span>Java<\/span>\r\n\t\t\t\t\t\t\t\t\t\r\n\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\r\n\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\r\n\t\t\t\t\t\t\t\t\t\r\n\t\t\t\t\t\t\t\t<\/a>\r\n\t\t\t\t\t\t\t<\/li>\r\n\t\t\t\t\t\t\t\t\t\t\t <\/ul>\r\n\r\n\t\t\t\t\t  <!-- Tab panes -->\r\n\t\t\t\t\t  <div class=\"tab-content\" id=\"tab-content_11622\">\r\n\t\t\t\t\t\t\t\t\t\t\t\t <div role=\"tabpanel\" class=\"tab-pane  in active \" id=\"tabs_desc_11622_1\">\r\n\t\t\t\t\t\t\t\t<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"java\">class Node {\r\n    int key;\r\n    Node left, right;\r\n\r\n    public Node(int item)\r\n    {\r\n        key = item;\r\n        left = right = null;\r\n    }\r\n}\r\n\r\nclass BinaryTree {\r\n    Node root;\r\n\r\n    BinaryTree() { root = null; }\r\n\r\n     void printPreorder(Node node)\r\n    {\r\n        if (node == null)\r\n            return;\r\n \r\n        System.out.print(node.key + \" \");\r\n        printPreorder(node.left);\r\n        printPreorder(node.right);\r\n    }\r\n \r\n    void printPreorder() { printPreorder(root); }\r\n    \r\n    void printInorder(Node node)\r\n    {\r\n        if (node == null)\r\n            return;\r\n\r\n        printInorder(node.left);\r\n        System.out.print(node.key + \" \");\r\n        printInorder(node.right);\r\n    }\r\n    \r\n    void printInorder() { printInorder(root); }\r\n    \r\n     void printPostorder(Node node)\r\n    {\r\n        if (node == null)\r\n            return;\r\n \r\n        printPostorder(node.left);\r\n        printPostorder(node.right);\r\n        System.out.print(node.key + \" \");\r\n    }\r\n \r\n    void printPostorder() { printPostorder(root); }\r\n\r\n    public static void main(String[] args)\r\n    {\r\n        BinaryTree tree = new BinaryTree();\r\n        tree.root = new Node(1);\r\n        tree.root.left = new Node(2);\r\n        tree.root.right = new Node(3);\r\n        tree.root.left.left = new Node(4);\r\n        tree.root.left.right = new Node(5);\r\n\r\n        \r\n        System.out.println(\"Preorder traversal of binary tree is \");\r\n        tree.printPreorder();\r\n        \r\n        System.out.println(\"&#92;nInorder traversal of binary tree is \");\r\n        tree.printInorder();\r\n        \r\n        System.out.println(\"&#92;nPostorder traversal of binary tree is \");\r\n        tree.printPostorder();\r\n    }\r\n}<\/pre>\t\t\t\t\t\t <\/div>\r\n\t\t\t\t\t\t\t\r\n\t\t\t\t\t <\/div>\r\n\t\t\t\t\t \r\n\t\t\t\t <\/div>\r\n <script>\r\n\t\tjQuery(function () {\r\n\t\t\tjQuery('#myTab_11622 a:first').tab('show')\r\n\t\t});\r\n\t\t\r\n\t\t\t\tjQuery(function(){\r\n\t\t\tvar b=\"fadeIn\";\r\n\t\t\tvar c;\r\n\t\t\tvar a;\r\n\t\t\td(jQuery(\"#myTab_11622 a\"),jQuery(\"#tab-content_11622\"));function d(e,f,g){\r\n\t\t\t\te.click(function(i){\r\n\t\t\t\t\ti.preventDefault();\r\n\t\t\t\t\tjQuery(this).tab(\"show\");\r\n\t\t\t\t\tvar h=jQuery(this).data(\"easein\");\r\n\t\t\t\t\tif(c){c.removeClass(a);}\r\n\t\t\t\t\tif(h){f.find(\"div.active\").addClass(\"animated \"+h);a=h;}\r\n\t\t\t\t\telse{if(g){f.find(\"div.active\").addClass(\"animated \"+g);a=g;}else{f.find(\"div.active\").addClass(\"animated \"+b);a=b;}}c=f.find(\"div.active\");\r\n\t\t\t\t});\r\n\t\t\t}\r\n\t\t});\r\n\t\t\r\n\r\n\t\tfunction do_resize(){\r\n\r\n\t\t\tvar width=jQuery( '.tab-content .tab-pane iframe' ).width();\r\n\t\t\tvar height=jQuery( '.tab-content .tab-pane iframe' ).height();\r\n\r\n\t\t\tvar toggleSize = true;\r\n\t\t\tjQuery('iframe').animate({\r\n\t\t\t    width: toggleSize ? width : 640,\r\n\t\t\t    height: toggleSize ? height : 360\r\n\t\t\t  }, 250);\r\n\r\n\t\t\t  toggleSize = !toggleSize;\r\n\t\t}\r\n\r\n\r\n\t<\/script>\r\n\t\t\t\t\r\n\t\t\t\n<p><strong>Conclusion<\/strong><br \/>\nSo, 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.<\/p>\n<p>Let us now look at some Frequently Asked Questions (FAQs)<\/p>\n<h2>FAQs<\/h2>\n<p><strong>1. Give one application of the tree data structure.<\/strong><br \/>\nThe 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.<\/p>\n<p><strong>2. Why is the node of the tree data structure called self-referential?<\/strong><br \/>\nSelf-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.<\/p>\n<p><strong>3. What is the Time Complexity of Tree Traversal in BST?<\/strong><br \/>\nWhether 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).<\/p>\n","protected":false},"excerpt":{"rendered":"<p>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\u2019s 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 [&hellip;]<\/p>\n","protected":false},"author":52,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"_monsterinsights_skip_tracking":false,"_monsterinsights_sitenote_active":false,"_monsterinsights_sitenote_note":"","_monsterinsights_sitenote_category":0,"footnotes":""},"categories":[153],"tags":[],"class_list":["post-11675","post","type-post","status-publish","format-standard","hentry","category-tree"],"yoast_head":"<!-- This site is optimized with the Yoast SEO plugin v25.8 - https:\/\/yoast.com\/wordpress\/plugins\/seo\/ -->\n<title>Tree in Data Structure: Definition, Types, and Traversing<\/title>\n<meta name=\"description\" content=\"Understanding what a tree data structure is, what are its different types, and different tree traversals.\" \/>\n<meta name=\"robots\" content=\"index, follow, max-snippet:-1, max-image-preview:large, max-video-preview:-1\" \/>\n<link rel=\"canonical\" href=\"https:\/\/prepbytes.com\/blog\/tree-in-data-structure-definition-types-and-traversing\/\" \/>\n<meta property=\"og:locale\" content=\"en_US\" \/>\n<meta property=\"og:type\" content=\"article\" \/>\n<meta property=\"og:title\" content=\"Tree in Data Structure: Definition, Types, and Traversing\" \/>\n<meta property=\"og:description\" content=\"Understanding what a tree data structure is, what are its different types, and different tree traversals.\" \/>\n<meta property=\"og:url\" content=\"https:\/\/prepbytes.com\/blog\/tree-in-data-structure-definition-types-and-traversing\/\" \/>\n<meta property=\"og:site_name\" content=\"PrepBytes Blog\" \/>\n<meta property=\"article:publisher\" content=\"https:\/\/www.facebook.com\/prepbytes0211\/\" \/>\n<meta property=\"article:published_time\" content=\"2023-01-16T07:54:12+00:00\" \/>\n<meta property=\"og:image\" content=\"https:\/\/prepbytes-misc-images.s3.ap-south-1.amazonaws.com\/assets\/1673853546595-Tree%20in%20Data%20Structure.jpg\" \/>\n<meta name=\"author\" content=\"Prepbytes\" \/>\n<meta name=\"twitter:card\" content=\"summary_large_image\" \/>\n<meta name=\"twitter:label1\" content=\"Written by\" \/>\n\t<meta name=\"twitter:data1\" content=\"Prepbytes\" \/>\n\t<meta name=\"twitter:label2\" content=\"Est. reading time\" \/>\n\t<meta name=\"twitter:data2\" content=\"7 minutes\" \/>\n<script type=\"application\/ld+json\" class=\"yoast-schema-graph\">{\"@context\":\"https:\/\/schema.org\",\"@graph\":[{\"@type\":\"Article\",\"@id\":\"https:\/\/prepbytes.com\/blog\/tree-in-data-structure-definition-types-and-traversing\/#article\",\"isPartOf\":{\"@id\":\"https:\/\/prepbytes.com\/blog\/tree-in-data-structure-definition-types-and-traversing\/\"},\"author\":{\"name\":\"Prepbytes\",\"@id\":\"http:\/\/43.205.93.38\/#\/schema\/person\/3f7dc4ae851791d5947a7f99df363d5e\"},\"headline\":\"Tree in Data Structure: Definition, Types, and Traversing\",\"datePublished\":\"2023-01-16T07:54:12+00:00\",\"mainEntityOfPage\":{\"@id\":\"https:\/\/prepbytes.com\/blog\/tree-in-data-structure-definition-types-and-traversing\/\"},\"wordCount\":1485,\"commentCount\":0,\"publisher\":{\"@id\":\"http:\/\/43.205.93.38\/#organization\"},\"image\":{\"@id\":\"https:\/\/prepbytes.com\/blog\/tree-in-data-structure-definition-types-and-traversing\/#primaryimage\"},\"thumbnailUrl\":\"https:\/\/prepbytes-misc-images.s3.ap-south-1.amazonaws.com\/assets\/1673853546595-Tree%20in%20Data%20Structure.jpg\",\"articleSection\":[\"Trees\"],\"inLanguage\":\"en-US\",\"potentialAction\":[{\"@type\":\"CommentAction\",\"name\":\"Comment\",\"target\":[\"https:\/\/prepbytes.com\/blog\/tree-in-data-structure-definition-types-and-traversing\/#respond\"]}]},{\"@type\":\"WebPage\",\"@id\":\"https:\/\/prepbytes.com\/blog\/tree-in-data-structure-definition-types-and-traversing\/\",\"url\":\"https:\/\/prepbytes.com\/blog\/tree-in-data-structure-definition-types-and-traversing\/\",\"name\":\"Tree in Data Structure: Definition, Types, and Traversing\",\"isPartOf\":{\"@id\":\"http:\/\/43.205.93.38\/#website\"},\"primaryImageOfPage\":{\"@id\":\"https:\/\/prepbytes.com\/blog\/tree-in-data-structure-definition-types-and-traversing\/#primaryimage\"},\"image\":{\"@id\":\"https:\/\/prepbytes.com\/blog\/tree-in-data-structure-definition-types-and-traversing\/#primaryimage\"},\"thumbnailUrl\":\"https:\/\/prepbytes-misc-images.s3.ap-south-1.amazonaws.com\/assets\/1673853546595-Tree%20in%20Data%20Structure.jpg\",\"datePublished\":\"2023-01-16T07:54:12+00:00\",\"description\":\"Understanding what a tree data structure is, what are its different types, and different tree traversals.\",\"breadcrumb\":{\"@id\":\"https:\/\/prepbytes.com\/blog\/tree-in-data-structure-definition-types-and-traversing\/#breadcrumb\"},\"inLanguage\":\"en-US\",\"potentialAction\":[{\"@type\":\"ReadAction\",\"target\":[\"https:\/\/prepbytes.com\/blog\/tree-in-data-structure-definition-types-and-traversing\/\"]}]},{\"@type\":\"ImageObject\",\"inLanguage\":\"en-US\",\"@id\":\"https:\/\/prepbytes.com\/blog\/tree-in-data-structure-definition-types-and-traversing\/#primaryimage\",\"url\":\"https:\/\/prepbytes-misc-images.s3.ap-south-1.amazonaws.com\/assets\/1673853546595-Tree%20in%20Data%20Structure.jpg\",\"contentUrl\":\"https:\/\/prepbytes-misc-images.s3.ap-south-1.amazonaws.com\/assets\/1673853546595-Tree%20in%20Data%20Structure.jpg\"},{\"@type\":\"BreadcrumbList\",\"@id\":\"https:\/\/prepbytes.com\/blog\/tree-in-data-structure-definition-types-and-traversing\/#breadcrumb\",\"itemListElement\":[{\"@type\":\"ListItem\",\"position\":1,\"name\":\"Home\",\"item\":\"http:\/\/43.205.93.38\/\"},{\"@type\":\"ListItem\",\"position\":2,\"name\":\"Trees\",\"item\":\"https:\/\/prepbytes.com\/blog\/category\/tree\/\"},{\"@type\":\"ListItem\",\"position\":3,\"name\":\"Tree in Data Structure: Definition, Types, and Traversing\"}]},{\"@type\":\"WebSite\",\"@id\":\"http:\/\/43.205.93.38\/#website\",\"url\":\"http:\/\/43.205.93.38\/\",\"name\":\"PrepBytes Blog\",\"description\":\"ONE-STOP RESOURCE FOR EVERYTHING RELATED TO CODING\",\"publisher\":{\"@id\":\"http:\/\/43.205.93.38\/#organization\"},\"potentialAction\":[{\"@type\":\"SearchAction\",\"target\":{\"@type\":\"EntryPoint\",\"urlTemplate\":\"http:\/\/43.205.93.38\/?s={search_term_string}\"},\"query-input\":{\"@type\":\"PropertyValueSpecification\",\"valueRequired\":true,\"valueName\":\"search_term_string\"}}],\"inLanguage\":\"en-US\"},{\"@type\":\"Organization\",\"@id\":\"http:\/\/43.205.93.38\/#organization\",\"name\":\"Prepbytes\",\"url\":\"http:\/\/43.205.93.38\/\",\"logo\":{\"@type\":\"ImageObject\",\"inLanguage\":\"en-US\",\"@id\":\"http:\/\/43.205.93.38\/#\/schema\/logo\/image\/\",\"url\":\"https:\/\/blog.prepbytes.com\/wp-content\/uploads\/2025\/07\/uzxxllgloialmn9mhwfe.webp\",\"contentUrl\":\"https:\/\/blog.prepbytes.com\/wp-content\/uploads\/2025\/07\/uzxxllgloialmn9mhwfe.webp\",\"width\":160,\"height\":160,\"caption\":\"Prepbytes\"},\"image\":{\"@id\":\"http:\/\/43.205.93.38\/#\/schema\/logo\/image\/\"},\"sameAs\":[\"https:\/\/www.facebook.com\/prepbytes0211\/\",\"https:\/\/www.instagram.com\/prepbytes\/\",\"https:\/\/www.linkedin.com\/company\/prepbytes\/\",\"https:\/\/www.youtube.com\/channel\/UC0xGnHDrjUM1pDEK2Ka5imA\"]},{\"@type\":\"Person\",\"@id\":\"http:\/\/43.205.93.38\/#\/schema\/person\/3f7dc4ae851791d5947a7f99df363d5e\",\"name\":\"Prepbytes\",\"image\":{\"@type\":\"ImageObject\",\"inLanguage\":\"en-US\",\"@id\":\"http:\/\/43.205.93.38\/#\/schema\/person\/image\/\",\"url\":\"https:\/\/secure.gravatar.com\/avatar\/232042cd1a1ea0e982c96d2a2ec93fb70a8e864e00784491231e7bfe5a9e06b5?s=96&d=mm&r=g\",\"contentUrl\":\"https:\/\/secure.gravatar.com\/avatar\/232042cd1a1ea0e982c96d2a2ec93fb70a8e864e00784491231e7bfe5a9e06b5?s=96&d=mm&r=g\",\"caption\":\"Prepbytes\"},\"url\":\"https:\/\/prepbytes.com\/blog\/author\/gourav-jaincollegedekho-com\/\"}]}<\/script>\n<!-- \/ Yoast SEO plugin. -->","yoast_head_json":{"title":"Tree in Data Structure: Definition, Types, and Traversing","description":"Understanding what a tree data structure is, what are its different types, and different tree traversals.","robots":{"index":"index","follow":"follow","max-snippet":"max-snippet:-1","max-image-preview":"max-image-preview:large","max-video-preview":"max-video-preview:-1"},"canonical":"https:\/\/prepbytes.com\/blog\/tree-in-data-structure-definition-types-and-traversing\/","og_locale":"en_US","og_type":"article","og_title":"Tree in Data Structure: Definition, Types, and Traversing","og_description":"Understanding what a tree data structure is, what are its different types, and different tree traversals.","og_url":"https:\/\/prepbytes.com\/blog\/tree-in-data-structure-definition-types-and-traversing\/","og_site_name":"PrepBytes Blog","article_publisher":"https:\/\/www.facebook.com\/prepbytes0211\/","article_published_time":"2023-01-16T07:54:12+00:00","og_image":[{"url":"https:\/\/prepbytes-misc-images.s3.ap-south-1.amazonaws.com\/assets\/1673853546595-Tree%20in%20Data%20Structure.jpg","type":"","width":"","height":""}],"author":"Prepbytes","twitter_card":"summary_large_image","twitter_misc":{"Written by":"Prepbytes","Est. reading time":"7 minutes"},"schema":{"@context":"https:\/\/schema.org","@graph":[{"@type":"Article","@id":"https:\/\/prepbytes.com\/blog\/tree-in-data-structure-definition-types-and-traversing\/#article","isPartOf":{"@id":"https:\/\/prepbytes.com\/blog\/tree-in-data-structure-definition-types-and-traversing\/"},"author":{"name":"Prepbytes","@id":"http:\/\/43.205.93.38\/#\/schema\/person\/3f7dc4ae851791d5947a7f99df363d5e"},"headline":"Tree in Data Structure: Definition, Types, and Traversing","datePublished":"2023-01-16T07:54:12+00:00","mainEntityOfPage":{"@id":"https:\/\/prepbytes.com\/blog\/tree-in-data-structure-definition-types-and-traversing\/"},"wordCount":1485,"commentCount":0,"publisher":{"@id":"http:\/\/43.205.93.38\/#organization"},"image":{"@id":"https:\/\/prepbytes.com\/blog\/tree-in-data-structure-definition-types-and-traversing\/#primaryimage"},"thumbnailUrl":"https:\/\/prepbytes-misc-images.s3.ap-south-1.amazonaws.com\/assets\/1673853546595-Tree%20in%20Data%20Structure.jpg","articleSection":["Trees"],"inLanguage":"en-US","potentialAction":[{"@type":"CommentAction","name":"Comment","target":["https:\/\/prepbytes.com\/blog\/tree-in-data-structure-definition-types-and-traversing\/#respond"]}]},{"@type":"WebPage","@id":"https:\/\/prepbytes.com\/blog\/tree-in-data-structure-definition-types-and-traversing\/","url":"https:\/\/prepbytes.com\/blog\/tree-in-data-structure-definition-types-and-traversing\/","name":"Tree in Data Structure: Definition, Types, and Traversing","isPartOf":{"@id":"http:\/\/43.205.93.38\/#website"},"primaryImageOfPage":{"@id":"https:\/\/prepbytes.com\/blog\/tree-in-data-structure-definition-types-and-traversing\/#primaryimage"},"image":{"@id":"https:\/\/prepbytes.com\/blog\/tree-in-data-structure-definition-types-and-traversing\/#primaryimage"},"thumbnailUrl":"https:\/\/prepbytes-misc-images.s3.ap-south-1.amazonaws.com\/assets\/1673853546595-Tree%20in%20Data%20Structure.jpg","datePublished":"2023-01-16T07:54:12+00:00","description":"Understanding what a tree data structure is, what are its different types, and different tree traversals.","breadcrumb":{"@id":"https:\/\/prepbytes.com\/blog\/tree-in-data-structure-definition-types-and-traversing\/#breadcrumb"},"inLanguage":"en-US","potentialAction":[{"@type":"ReadAction","target":["https:\/\/prepbytes.com\/blog\/tree-in-data-structure-definition-types-and-traversing\/"]}]},{"@type":"ImageObject","inLanguage":"en-US","@id":"https:\/\/prepbytes.com\/blog\/tree-in-data-structure-definition-types-and-traversing\/#primaryimage","url":"https:\/\/prepbytes-misc-images.s3.ap-south-1.amazonaws.com\/assets\/1673853546595-Tree%20in%20Data%20Structure.jpg","contentUrl":"https:\/\/prepbytes-misc-images.s3.ap-south-1.amazonaws.com\/assets\/1673853546595-Tree%20in%20Data%20Structure.jpg"},{"@type":"BreadcrumbList","@id":"https:\/\/prepbytes.com\/blog\/tree-in-data-structure-definition-types-and-traversing\/#breadcrumb","itemListElement":[{"@type":"ListItem","position":1,"name":"Home","item":"http:\/\/43.205.93.38\/"},{"@type":"ListItem","position":2,"name":"Trees","item":"https:\/\/prepbytes.com\/blog\/category\/tree\/"},{"@type":"ListItem","position":3,"name":"Tree in Data Structure: Definition, Types, and Traversing"}]},{"@type":"WebSite","@id":"http:\/\/43.205.93.38\/#website","url":"http:\/\/43.205.93.38\/","name":"PrepBytes Blog","description":"ONE-STOP RESOURCE FOR EVERYTHING RELATED TO CODING","publisher":{"@id":"http:\/\/43.205.93.38\/#organization"},"potentialAction":[{"@type":"SearchAction","target":{"@type":"EntryPoint","urlTemplate":"http:\/\/43.205.93.38\/?s={search_term_string}"},"query-input":{"@type":"PropertyValueSpecification","valueRequired":true,"valueName":"search_term_string"}}],"inLanguage":"en-US"},{"@type":"Organization","@id":"http:\/\/43.205.93.38\/#organization","name":"Prepbytes","url":"http:\/\/43.205.93.38\/","logo":{"@type":"ImageObject","inLanguage":"en-US","@id":"http:\/\/43.205.93.38\/#\/schema\/logo\/image\/","url":"https:\/\/blog.prepbytes.com\/wp-content\/uploads\/2025\/07\/uzxxllgloialmn9mhwfe.webp","contentUrl":"https:\/\/blog.prepbytes.com\/wp-content\/uploads\/2025\/07\/uzxxllgloialmn9mhwfe.webp","width":160,"height":160,"caption":"Prepbytes"},"image":{"@id":"http:\/\/43.205.93.38\/#\/schema\/logo\/image\/"},"sameAs":["https:\/\/www.facebook.com\/prepbytes0211\/","https:\/\/www.instagram.com\/prepbytes\/","https:\/\/www.linkedin.com\/company\/prepbytes\/","https:\/\/www.youtube.com\/channel\/UC0xGnHDrjUM1pDEK2Ka5imA"]},{"@type":"Person","@id":"http:\/\/43.205.93.38\/#\/schema\/person\/3f7dc4ae851791d5947a7f99df363d5e","name":"Prepbytes","image":{"@type":"ImageObject","inLanguage":"en-US","@id":"http:\/\/43.205.93.38\/#\/schema\/person\/image\/","url":"https:\/\/secure.gravatar.com\/avatar\/232042cd1a1ea0e982c96d2a2ec93fb70a8e864e00784491231e7bfe5a9e06b5?s=96&d=mm&r=g","contentUrl":"https:\/\/secure.gravatar.com\/avatar\/232042cd1a1ea0e982c96d2a2ec93fb70a8e864e00784491231e7bfe5a9e06b5?s=96&d=mm&r=g","caption":"Prepbytes"},"url":"https:\/\/prepbytes.com\/blog\/author\/gourav-jaincollegedekho-com\/"}]}},"_links":{"self":[{"href":"https:\/\/prepbytes.com\/blog\/wp-json\/wp\/v2\/posts\/11675","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/prepbytes.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/prepbytes.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/prepbytes.com\/blog\/wp-json\/wp\/v2\/users\/52"}],"replies":[{"embeddable":true,"href":"https:\/\/prepbytes.com\/blog\/wp-json\/wp\/v2\/comments?post=11675"}],"version-history":[{"count":2,"href":"https:\/\/prepbytes.com\/blog\/wp-json\/wp\/v2\/posts\/11675\/revisions"}],"predecessor-version":[{"id":11750,"href":"https:\/\/prepbytes.com\/blog\/wp-json\/wp\/v2\/posts\/11675\/revisions\/11750"}],"wp:attachment":[{"href":"https:\/\/prepbytes.com\/blog\/wp-json\/wp\/v2\/media?parent=11675"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/prepbytes.com\/blog\/wp-json\/wp\/v2\/categories?post=11675"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/prepbytes.com\/blog\/wp-json\/wp\/v2\/tags?post=11675"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}