![\"\"](\"https:\/\/prepbytes-misc-images.s3.ap-south-1.amazonaws.com\/assets\/1673530844021-What%20is%20Binary%20Tree%20in%20Data%20Structure.jpg\")
<\/p>\n<\/p>\n
In this article, we will discuss binary tree in data structure. This is one of the most important topics of data structure.<\/p>\n
A binary tree is a tree data structure in which each parent node can have at most two children. Each node of a binary tree consists of three items:<\/p>\n
![\"\"](\"https:\/\/prepbytes-misc-images.s3.ap-south-1.amazonaws.com\/assets\/1673530844120-What%20is%20Binary%20Tree%20in%20Data%20Structure1.png\")
<\/p>\n
Structure of Node<\/strong><\/p>\n A full Binary tree is a special type of binary tree in which every parent node\/internal node has either two or no children.<\/p>\n A perfect binary tree is a type of binary tree in which every internal node has exactly two child nodes and all the leaf nodes are at the same level.<\/p>\n A complete binary tree is just like a full binary tree, but with two major differences<\/p>\n A skewed binary tree is a pathological\/degenerate tree in which the tree is either dominated by the left nodes or the right nodes. Thus, there are two types of skewed binary tree: left-skewed binary tree and right-skewed binary tree.<\/strong><\/p>\n It is a type of binary tree in which the difference between the height of the left and the right subtree for each node is either 0 or 1.<\/p>\n A node in a binary tree is represented by a structure containing data and two pointers to other structures of the same type. It is a type of binary tree because each tree node has at most two children. It is called a search tree because it can be used to search for the existence of a number in O(log(n))<\/strong> time.<\/p>\n The properties that separate binary search trees from regular binary trees are<\/p>\n The algorithm relies on the property of BST where all left subtrees have values \u200b\u200bbelow the root and all right subtrees have values \u200b\u200babove the root. Time Complexity<\/strong><\/p>\n Here, n is the number of nodes in the tree.<\/strong><\/p>\n Space Complexity:<\/strong> The space complexity for all the operations is O(n).<\/p>\n A binary tree is a data structure in which data is stored in a hierarchical form. Traversal of the binary tree means visiting every node of the tree. The process of accessing the nodes of a tree in some order is called a traversal of a binary tree. Any process for visiting all of the nodes is called a traversal.<\/p>\n Unlike linear data structures(Array, Queues, Linked List, Queues, etc.) that have only one way to traverse them but the tree data structure can be traversed in multiple ways. 1. In-order Traversal<\/strong> Step 1:<\/strong> Firstly left subtree is visited An in-order traversal of the Binary Search Tree gives us the ascending order of values stored in the tree.<\/strong><\/p>\n 2. Pre-order Traversal<\/strong> Step 1:<\/strong> Firstly root is visited 3. Post-order Traversal<\/strong> Step 1:<\/strong> Firstly left subtree is visited Traversal Implementation in C++<\/strong><\/p>\n\t\t\t\t\t\tstructure node\n{\nint data;\nstructure node *left;\nstructure node *right;\n};<\/code><\/pre>\nTypes of Binary Tree<\/h2>\n
1. Full Binary Tree<\/h3>\n
![\"\"](\"https:\/\/prepbytes-misc-images.s3.ap-south-1.amazonaws.com\/assets\/1673530844120-What%20is%20Binary%20Tree%20in%20Data%20Structure2.png\")
<\/p>\n2. Perfect Binary Tree<\/h3>\n
![\"\"](\"https:\/\/prepbytes-misc-images.s3.ap-south-1.amazonaws.com\/assets\/1673530844129-What%20is%20Binary%20Tree%20in%20Data%20Structure3.png\")
<\/p>\n3. Complete Binary Tree<\/h3>\n
\n
![\"\"](\"https:\/\/prepbytes-misc-images.s3.ap-south-1.amazonaws.com\/assets\/1673530844130-What%20is%20Binary%20Tree%20in%20Data%20Structure4.png\")
<\/p>\n5. Skewed Binary Tree<\/h3>\n
![\"\"](\"https:\/\/prepbytes-misc-images.s3.ap-south-1.amazonaws.com\/assets\/1673530844130-What%20is%20Binary%20Tree%20in%20Data%20Structure5.png\")
<\/p>\n6. Balanced Binary Tree<\/h3>\n
![\"\"](\"https:\/\/prepbytes-misc-images.s3.ap-south-1.amazonaws.com\/assets\/1673530844130-What%20is%20Binary%20Tree%20in%20Data%20Structure6.png\")
<\/p>\nBinary search tree in data structure<\/h2>\n
\n
Algorithm of Search Operation<\/h3>\n
\nIf the value is less than the root, we can say for sure that the value is not in the right subtree; we need to only search in the left subtree and if the value is above the root, we can say for sure that the value is not in the left subtree; we need to only search in the right subtree.<\/p>\nBinary Search Tree Complexities<\/h3>\n
\n\n
\n \nOperation<\/th>\n Best Case Complexity<\/th>\n Average Case Complexity<\/th>\n Worst Case Complexity<\/th>\n<\/tr>\n<\/thead>\n \n Search<\/td>\n O(log n)<\/td>\n O(log n)<\/td>\n O(n)<\/td>\n<\/tr>\n \n Insertion<\/td>\n O(log n)<\/td>\n O(log n)<\/td>\n O(n)<\/td>\n<\/tr>\n \n Deletion<\/td>\n O(log n)<\/td>\n O(log n)<\/td>\n O(n)<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n Binary tree traversal in data structure<\/h2>\n
What is the Traversal of a Binary Tree?<\/h3>\n
What is Traversal Order?<\/h3>\n
\nThe tree can be traversed in three ways:<\/strong><\/p>\n
\nIn inorder traversal of the binary tree, these 3 steps are recursively performed.<\/p>\n
\nStep 2:<\/strong> Then the root is visited
\nStep 3:<\/strong> Then the right subtree is visited.<\/p>\n
\nIn pre-order traversal of a binary tree, these 3 steps are recursively performed.<\/p>\n
\nStep 2:<\/strong> Then the left subtree is visited
\nStep 3:<\/strong> Then finally the right subtree is visited.<\/p>\n
\nIn post-order traversal of the binary tree root node is visited at the last. In this traversal, these 3 steps are recursively performed.<\/p>\n
\nStep 2:<\/strong> Then the right subtree is visited.
\nStep 3:<\/strong> And at last, the root is visited.<\/p>\nWhat are Tree Traversal Methods?<\/h3>\n