{"id":98382,"date":"2021-07-21T09:00:34","date_gmt":"2021-07-21T03:30:34","guid":{"rendered":"https:\/\/data-flair.training\/blogs\/?p=98382"},"modified":"2021-07-20T13:45:51","modified_gmt":"2021-07-20T08:15:51","slug":"tree-data-structure","status":"publish","type":"post","link":"https:\/\/data-flair.training\/blogs\/tree-data-structure\/","title":{"rendered":"Tree Data Structure"},"content":{"rendered":"<p>Tree, just like graph, is also a nonlinear data structure. The elements are not arranged in a sequential manner. In this article, we will learn about trees, different terminologies, types of trees, and their applications.<\/p>\n<h3>Tree Data Structure<\/h3>\n<p>A tree is a nonlinear and hierarchical data structure. A tree consists of nodes and edges. Tree data structures, just like graphs are nonlinear data structures. The computation complexity increases exponentially while working with large data stored in a linear data structure like an array or linked list. But the use of trees makes it highly efficient, fast, and time-efficient.<\/p>\n<ul>\n<li>Different tree structures perform faster and allow quicker access to data<\/li>\n<li>Each tree has one root node and each node can have only one parent.<\/li>\n<li>A tree is not a sequential data structure. It is a hierarchical structure as elements in a Tree are arranged in multiple levels<\/li>\n<\/ul>\n<p><a href=\"https:\/\/data-flair.training\/blogs\/wp-content\/uploads\/sites\/2\/2021\/07\/DS-Tree-normla-image01.jpg\"><img loading=\"lazy\" decoding=\"async\" class=\"aligncenter size-full wp-image-98537\" src=\"https:\/\/data-flair.training\/blogs\/wp-content\/uploads\/sites\/2\/2021\/07\/DS-Tree-normla-image01.jpg\" alt=\"data structure tree\" width=\"334\" height=\"300\" srcset=\"https:\/\/data-flair.training\/blogs\/wp-content\/uploads\/sites\/2\/2021\/07\/DS-Tree-normla-image01.jpg 334w, https:\/\/data-flair.training\/blogs\/wp-content\/uploads\/sites\/2\/2021\/07\/DS-Tree-normla-image01-320x287.jpg 320w\" sizes=\"auto, (max-width: 334px) 100vw, 334px\" \/><\/a><\/p>\n<h3>Tree Terminologies<\/h3>\n<p>1. <strong>Node<\/strong>: Entity containing a key \/ Value and pointer to its children nodes.<\/p>\n<p>2. <strong>Edge<\/strong>: the connection between any two nodes.<\/p>\n<p>3. <strong>Root<\/strong>: root is the topmost node of the tree. Each tree has only one root node.<\/p>\n<p>4. <strong>Height of a node<\/strong>: height is the number of edges in the longest path from the node to the leaf node.<\/p>\n<p>5. <strong>Depth of a node<\/strong>: Number of edges from the root node to the node.<\/p>\n<p>6. <strong>Height of a tree:<\/strong> number of edges from the root to the leaf node.<\/p>\n<p>7. <strong>Degree of a node:<\/strong> total number of branches a node is having<\/p>\n<p>8. <strong>Forest<\/strong>: Collection of disjoint trees<\/p>\n<p>9. <strong>Traversal<\/strong>: Visiting any node in the tree from the root node is called traversal.<\/p>\n<p><a href=\"https:\/\/data-flair.training\/blogs\/wp-content\/uploads\/sites\/2\/2021\/07\/DS-Tree-normla-image02.jpg\"><img loading=\"lazy\" decoding=\"async\" class=\"aligncenter size-full wp-image-98538\" src=\"https:\/\/data-flair.training\/blogs\/wp-content\/uploads\/sites\/2\/2021\/07\/DS-Tree-normla-image02.jpg\" alt=\"Tree Terminologies\" width=\"802\" height=\"540\" srcset=\"https:\/\/data-flair.training\/blogs\/wp-content\/uploads\/sites\/2\/2021\/07\/DS-Tree-normla-image02.jpg 802w, https:\/\/data-flair.training\/blogs\/wp-content\/uploads\/sites\/2\/2021\/07\/DS-Tree-normla-image02-768x517.jpg 768w, https:\/\/data-flair.training\/blogs\/wp-content\/uploads\/sites\/2\/2021\/07\/DS-Tree-normla-image02-720x485.jpg 720w, https:\/\/data-flair.training\/blogs\/wp-content\/uploads\/sites\/2\/2021\/07\/DS-Tree-normla-image02-520x350.jpg 520w, https:\/\/data-flair.training\/blogs\/wp-content\/uploads\/sites\/2\/2021\/07\/DS-Tree-normla-image02-320x215.jpg 320w, https:\/\/data-flair.training\/blogs\/wp-content\/uploads\/sites\/2\/2021\/07\/DS-Tree-normla-image02-272x182.jpg 272w\" sizes=\"auto, (max-width: 802px) 100vw, 802px\" \/><\/a><\/p>\n<h3>Properties of Tree<\/h3>\n<p>1. A tree with n nodes will have n-1 edges. Each edge represents the path from one node to another.<\/p>\n<p>2. Each node except the root node will have at least one incoming edge and each node except the leaf nodes will have at least one outgoing edge. Each edge will represent the parent-child relationship<\/p>\n<p>3. The root node has zero depth. The depth of each node is defined as the length of the path from the root to that node<\/p>\n<p>4. Each leaf node has a height of 0. The height of each node is defined as the path from that node to the leaf node.<\/p>\n<h3>Types of tree in Data Structure<\/h3>\n<p><strong>1. Binary tree:<\/strong> in the binary tree, as the name suggests, each node can have at most two child nodes. A node can have zero, one, or two child nodes<\/p>\n<p><strong>2. General tree:<\/strong> general tree is one of the types of tree data structure in which a node can have any number of nodes. No restrictions on the degree of a node.<\/p>\n<p><strong>3. Binary search tree:<\/strong> binary search tree is a type of binary tree where each left node should have a value of less than the root node and each right node should have a value greater than the root node.<\/p>\n<p><strong>4. AVL tree:<\/strong> AVL tree is a variant of the binary search tree. It satisfies the property of both binary tree and binary search tree. Invented by Adelson Velsky Lindas, the AVL tree is a self-balancing binary search tree that balances the height of the left subtree and right subtrees. The balancing is measured in terms of the balancing factors.<\/p>\n<p><strong>5. Red Black tree:<\/strong> red-black tree is an improvement of the AVL tree. In the AVL tree, the Number of rotations required to balance the tree is not known but in a red-black tree, we can balance the tree in a maximum of two rotations. A red-black tree has one extra bit representing the red or black color of the node which ensures the balancing of the tree.<\/p>\n<p><strong>6. Splay tree:<\/strong> splay tree is a kind of binary search tree where the most recently accessed node is put at the root position by performing rotations. Just like the AVL tree, it is also a self-balancing binary search tree.<\/p>\n<p><strong>7. Treap:<\/strong> it is a combination of tree and heap data structure and satisfies the properties of both. Entry status structure each node has both key and priority associated with it. Key is derived from the binary search tree and priority is derived from the heap data structure.<\/p>\n<p><strong>8. B-Tree:<\/strong> B-tree is a balanced \u2018m\u2019 way tree where \u2018m\u2019 is the order of the tree. In the B tree, each node can have more than one key and more than two children. Each node can have maximum \u2018m\u2019 children and maximum and m-1 keys.<\/p>\n<h3>Implementation of tree<\/h3>\n<p>Each node in a tree has a pointer to each child node and data.<\/p>\n<p><a href=\"https:\/\/data-flair.training\/blogs\/wp-content\/uploads\/sites\/2\/2021\/07\/DS-Tree-normla-image03.jpg\"><img loading=\"lazy\" decoding=\"async\" class=\"aligncenter size-full wp-image-98539\" src=\"https:\/\/data-flair.training\/blogs\/wp-content\/uploads\/sites\/2\/2021\/07\/DS-Tree-normla-image03.jpg\" alt=\"Implementation of Tree in Data Structure\" width=\"576\" height=\"256\" srcset=\"https:\/\/data-flair.training\/blogs\/wp-content\/uploads\/sites\/2\/2021\/07\/DS-Tree-normla-image03.jpg 576w, https:\/\/data-flair.training\/blogs\/wp-content\/uploads\/sites\/2\/2021\/07\/DS-Tree-normla-image03-520x231.jpg 520w, https:\/\/data-flair.training\/blogs\/wp-content\/uploads\/sites\/2\/2021\/07\/DS-Tree-normla-image03-320x142.jpg 320w\" sizes=\"auto, (max-width: 576px) 100vw, 576px\" \/><\/a><\/p>\n<p>A node can be created as:<\/p>\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"generic\">struct node  \r\n{  \r\n  int data;  \r\nstruct node *leftchild;  \r\nstruct node *rightchild;   \r\n}<\/pre>\n<h3>Applications of tree<\/h3>\n<p>1. Heap data structure is useful in sorting<\/p>\n<p>2. Binary search trees are useful to check if the element present is or not. BST has a complexity of log n.<\/p>\n<p>3. Most popular databases use B trees and B+ trees<\/p>\n<p>4. Compilers use a syntax tree to validate the syntax of a program<\/p>\n<p>5. A modified version of trees called tries is used in modern routers to store routing information<\/p>\n<p>6. File stored in any folder on any drive on a hard disk is stored in a hierarchical form which uses a tree to store data.<\/p>\n<h3>Conclusion<\/h3>\n<p>Trees are non-linear data structures that are very efficient while dealing with large data. In this article, we briefly learned about different types of trees. We also witnessed some real-life applications of trees. In future articles, we will learn about each type in detail with their implementations in different languages.<\/p>\n","protected":false},"excerpt":{"rendered":"<p>Tree, just like graph, is also a nonlinear data structure. The elements are not arranged in a sequential manner. In this article, we will learn about trees, different terminologies, types of trees, and their&#46;&#46;&#46;<\/p>\n","protected":false},"author":1,"featured_media":98536,"comment_status":"open","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[24020],"tags":[24800,24799,24797,24798],"class_list":["post-98382","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-data-structure-tutorials","tag-applications-of-tree","tag-implementation-of-tree","tag-tree-data-structure","tag-types-of-tree-in-data-structure"],"yoast_head":"<!-- This site is optimized with the Yoast SEO plugin v27.8 - https:\/\/yoast.com\/product\/yoast-seo-wordpress\/ -->\n<title>Tree Data Structure - DataFlair<\/title>\n<meta name=\"description\" content=\"Tree is non-linear data structure that is very efficient while dealing with large data. See different types of trees &amp; their applications\" \/>\n<meta name=\"robots\" content=\"index, follow, max-snippet:-1, max-image-preview:large, max-video-preview:-1\" \/>\n<link rel=\"canonical\" href=\"https:\/\/data-flair.training\/blogs\/tree-data-structure\/\" \/>\n<meta property=\"og:locale\" content=\"en_US\" \/>\n<meta property=\"og:type\" content=\"article\" \/>\n<meta property=\"og:title\" content=\"Tree Data Structure - DataFlair\" \/>\n<meta property=\"og:description\" content=\"Tree is non-linear data structure that is very efficient while dealing with large data. See different types of trees &amp; their applications\" \/>\n<meta property=\"og:url\" content=\"https:\/\/data-flair.training\/blogs\/tree-data-structure\/\" \/>\n<meta property=\"og:site_name\" content=\"DataFlair\" \/>\n<meta property=\"article:publisher\" content=\"https:\/\/www.facebook.com\/DataFlairWS\/\" \/>\n<meta property=\"article:published_time\" content=\"2021-07-21T03:30:34+00:00\" \/>\n<meta property=\"og:image\" content=\"https:\/\/data-flair.training\/blogs\/wp-content\/uploads\/sites\/2\/2021\/07\/DS-Tree.jpg\" \/>\n\t<meta property=\"og:image:width\" content=\"1200\" \/>\n\t<meta property=\"og:image:height\" content=\"628\" \/>\n\t<meta property=\"og:image:type\" content=\"image\/jpeg\" \/>\n<meta name=\"author\" content=\"DataFlair Team\" \/>\n<meta name=\"twitter:card\" content=\"summary_large_image\" \/>\n<meta name=\"twitter:creator\" content=\"@DataFlairWS\" \/>\n<meta name=\"twitter:site\" content=\"@DataFlairWS\" \/>\n<meta name=\"twitter:label1\" content=\"Written by\" \/>\n\t<meta name=\"twitter:data1\" content=\"DataFlair Team\" \/>\n\t<meta name=\"twitter:label2\" content=\"Est. reading time\" \/>\n\t<meta name=\"twitter:data2\" content=\"5 minutes\" \/>\n<!-- \/ Yoast SEO plugin. -->","yoast_head_json":{"title":"Tree Data Structure - DataFlair","description":"Tree is non-linear data structure that is very efficient while dealing with large data. See different types of trees & their applications","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:\/\/data-flair.training\/blogs\/tree-data-structure\/","og_locale":"en_US","og_type":"article","og_title":"Tree Data Structure - DataFlair","og_description":"Tree is non-linear data structure that is very efficient while dealing with large data. See different types of trees & their applications","og_url":"https:\/\/data-flair.training\/blogs\/tree-data-structure\/","og_site_name":"DataFlair","article_publisher":"https:\/\/www.facebook.com\/DataFlairWS\/","article_published_time":"2021-07-21T03:30:34+00:00","og_image":[{"width":1200,"height":628,"url":"https:\/\/data-flair.training\/blogs\/wp-content\/uploads\/sites\/2\/2021\/07\/DS-Tree.jpg","type":"image\/jpeg"}],"author":"DataFlair Team","twitter_card":"summary_large_image","twitter_creator":"@DataFlairWS","twitter_site":"@DataFlairWS","twitter_misc":{"Written by":"DataFlair Team","Est. reading time":"5 minutes"},"schema":{"@context":"https:\/\/schema.org","@graph":[{"@type":"Article","@id":"https:\/\/data-flair.training\/blogs\/tree-data-structure\/#article","isPartOf":{"@id":"https:\/\/data-flair.training\/blogs\/tree-data-structure\/"},"author":{"name":"DataFlair Team","@id":"https:\/\/data-flair.training\/blogs\/#\/schema\/person\/b49855299264df5e27e3ec6c2cd9fde9"},"headline":"Tree Data Structure","datePublished":"2021-07-21T03:30:34+00:00","mainEntityOfPage":{"@id":"https:\/\/data-flair.training\/blogs\/tree-data-structure\/"},"wordCount":900,"commentCount":0,"publisher":{"@id":"https:\/\/data-flair.training\/blogs\/#organization"},"image":{"@id":"https:\/\/data-flair.training\/blogs\/tree-data-structure\/#primaryimage"},"thumbnailUrl":"https:\/\/data-flair.training\/blogs\/wp-content\/uploads\/sites\/2\/2021\/07\/DS-Tree.jpg","keywords":["Applications of tree","Implementation of tree","Tree Data Structure","Types of tree in Data Structure"],"articleSection":["Data Structure Tutorials"],"inLanguage":"en-US","potentialAction":[{"@type":"CommentAction","name":"Comment","target":["https:\/\/data-flair.training\/blogs\/tree-data-structure\/#respond"]}]},{"@type":"WebPage","@id":"https:\/\/data-flair.training\/blogs\/tree-data-structure\/","url":"https:\/\/data-flair.training\/blogs\/tree-data-structure\/","name":"Tree Data Structure - DataFlair","isPartOf":{"@id":"https:\/\/data-flair.training\/blogs\/#website"},"primaryImageOfPage":{"@id":"https:\/\/data-flair.training\/blogs\/tree-data-structure\/#primaryimage"},"image":{"@id":"https:\/\/data-flair.training\/blogs\/tree-data-structure\/#primaryimage"},"thumbnailUrl":"https:\/\/data-flair.training\/blogs\/wp-content\/uploads\/sites\/2\/2021\/07\/DS-Tree.jpg","datePublished":"2021-07-21T03:30:34+00:00","description":"Tree is non-linear data structure that is very efficient while dealing with large data. See different types of trees & their applications","breadcrumb":{"@id":"https:\/\/data-flair.training\/blogs\/tree-data-structure\/#breadcrumb"},"inLanguage":"en-US","potentialAction":[{"@type":"ReadAction","target":["https:\/\/data-flair.training\/blogs\/tree-data-structure\/"]}]},{"@type":"ImageObject","inLanguage":"en-US","@id":"https:\/\/data-flair.training\/blogs\/tree-data-structure\/#primaryimage","url":"https:\/\/data-flair.training\/blogs\/wp-content\/uploads\/sites\/2\/2021\/07\/DS-Tree.jpg","contentUrl":"https:\/\/data-flair.training\/blogs\/wp-content\/uploads\/sites\/2\/2021\/07\/DS-Tree.jpg","width":1200,"height":628,"caption":"Tree data structure"},{"@type":"BreadcrumbList","@id":"https:\/\/data-flair.training\/blogs\/tree-data-structure\/#breadcrumb","itemListElement":[{"@type":"ListItem","position":1,"name":"Blog Home","item":"https:\/\/data-flair.training\/blogs\/"},{"@type":"ListItem","position":2,"name":"Data Structure Tutorials","item":"https:\/\/data-flair.training\/blogs\/category\/data-structure-tutorials\/"},{"@type":"ListItem","position":3,"name":"Tree Data Structure"}]},{"@type":"WebSite","@id":"https:\/\/data-flair.training\/blogs\/#website","url":"https:\/\/data-flair.training\/blogs\/","name":"DataFlair","description":"Learn Today. Lead Tomorrow.","publisher":{"@id":"https:\/\/data-flair.training\/blogs\/#organization"},"potentialAction":[{"@type":"SearchAction","target":{"@type":"EntryPoint","urlTemplate":"https:\/\/data-flair.training\/blogs\/?s={search_term_string}"},"query-input":{"@type":"PropertyValueSpecification","valueRequired":true,"valueName":"search_term_string"}}],"inLanguage":"en-US"},{"@type":"Organization","@id":"https:\/\/data-flair.training\/blogs\/#organization","name":"DataFlair","url":"https:\/\/data-flair.training\/blogs\/","logo":{"@type":"ImageObject","inLanguage":"en-US","@id":"https:\/\/data-flair.training\/blogs\/#\/schema\/logo\/image\/","url":"https:\/\/data-flair.training\/blogs\/wp-content\/uploads\/sites\/2\/2016\/07\/Data-Flair.png","contentUrl":"https:\/\/data-flair.training\/blogs\/wp-content\/uploads\/sites\/2\/2016\/07\/Data-Flair.png","width":106,"height":48,"caption":"DataFlair"},"image":{"@id":"https:\/\/data-flair.training\/blogs\/#\/schema\/logo\/image\/"},"sameAs":["https:\/\/www.facebook.com\/DataFlairWS\/","https:\/\/x.com\/DataFlairWS","https:\/\/www.linkedin.com\/company\/dataflair-web-services-pvt-ltd\/","https:\/\/www.youtube.com\/user\/DataFlairWS"]},{"@type":"Person","@id":"https:\/\/data-flair.training\/blogs\/#\/schema\/person\/b49855299264df5e27e3ec6c2cd9fde9","name":"DataFlair Team","image":{"@type":"ImageObject","inLanguage":"en-US","@id":"https:\/\/secure.gravatar.com\/avatar\/ef46b745ddad2fad690af626c6ef29b91809ad0a9f5ef398d07817d8cad042f5?s=96&d=mm&r=g","url":"https:\/\/secure.gravatar.com\/avatar\/ef46b745ddad2fad690af626c6ef29b91809ad0a9f5ef398d07817d8cad042f5?s=96&d=mm&r=g","contentUrl":"https:\/\/secure.gravatar.com\/avatar\/ef46b745ddad2fad690af626c6ef29b91809ad0a9f5ef398d07817d8cad042f5?s=96&d=mm&r=g","caption":"DataFlair Team"},"description":"DataFlair Team is a group of passionate educators and industry experts dedicated to providing high-quality online learning resources on programming, Java, Python, C++, DSA, AI, ML, data Science, Android, Flutter, MERN, Web Development, and technology. With years of experience in the field, the team aims to simplify complex topics and help learners advance their careers. At DataFlair, we believe in empowering students and professionals with the knowledge and skills needed to thrive in today\u2019s fast-paced tech industry. Follow us for Free courses, expert insights, tutorials, and practical tips to boost your learning journey.","url":"https:\/\/data-flair.training\/blogs\/author\/datafbdad\/"}]}},"amp_enabled":true,"_links":{"self":[{"href":"https:\/\/data-flair.training\/blogs\/wp-json\/wp\/v2\/posts\/98382","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/data-flair.training\/blogs\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/data-flair.training\/blogs\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/data-flair.training\/blogs\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/data-flair.training\/blogs\/wp-json\/wp\/v2\/comments?post=98382"}],"version-history":[{"count":2,"href":"https:\/\/data-flair.training\/blogs\/wp-json\/wp\/v2\/posts\/98382\/revisions"}],"predecessor-version":[{"id":98540,"href":"https:\/\/data-flair.training\/blogs\/wp-json\/wp\/v2\/posts\/98382\/revisions\/98540"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/data-flair.training\/blogs\/wp-json\/wp\/v2\/media\/98536"}],"wp:attachment":[{"href":"https:\/\/data-flair.training\/blogs\/wp-json\/wp\/v2\/media?parent=98382"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/data-flair.training\/blogs\/wp-json\/wp\/v2\/categories?post=98382"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/data-flair.training\/blogs\/wp-json\/wp\/v2\/tags?post=98382"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}