Therefore, the maximum number of nodes at height 3 is equal to (1+2+4+8) = 15. The tree which is shown above has a height equal to 3. The height of the tree is defined as the longest path from the root node to the leaf node.At each level of i, the maximum number of nodes is 2 i.The nodes 3, 5 and 6 are the leaf nodes, so all these nodes contain NULL pointer on both left and right parts. The node 2 contains both the nodes (left and right node) therefore, it has two pointers (left and right). In the above tree, node 1 contains two pointers, i.e., left and a right pointer pointing to the left and right node respectively. The logical representation of the above tree is given below: The above tree is a binary tree because each node contains the utmost two children. Let's understand the binary tree through an example. Here, binary name itself suggests that 'two' therefore, each node can have either 0, 1 or 2 children. The pseudocode is given below.The Binary tree means that the node can have maximum two children. Pre-Order traversal: We visit the root node first, then recursively traverse the left subtree and recursively traverse the right subtree. (2) Recursively traverse its right subtree.ĭepending upon the order in which these operations occur, breadth-first traversal can be further divided into three categories. (1) Recursively traverse its left subtree. The algorithm for depth-first traversal is given below. In this way, we go deeper and deeper until there is no more child node left (i.e. In depth-first traversal, we visit the child nodes before visiting the next sibling. There are two types of traversal in a tree: (1) depth-first traversal and (2) breadth-first traversal. This memory waste can be avoided using a Threaded Binary Tree. More than half of the total nodes of a binary tree point to the null reference which is a huge waste of memory. Figure 7 shows a binary tree and its representation using the linked list.Īs you can see in the figure, all the leaf nodes’ references point to a null pointer. In linked list representation, each node of the tree holds the reference for left and right child. Fig 6 shows a binary tree and corresponding array representation. If i is the index of a parent, then the index of the left child is 2i + 1 and the index of the right child is 2i + 2. We need to allocate 2 h+1 - 1 array items, where h is the height of the tree, that can fit any kind of binary tree. The array representation is most suited for a complete binary tree where the waste of the memory is minimum. Using arrayĪ binary tree can be implemented efficiently using an array. One is the array representation and another is the linked list representation. There is two popular representation of a binary tree. One of the interesting property of a balanced tree is that the height of the tree is O(log n) which gives a guarantee that the insertion, deletion, and search operations are efficient. Examples of a balanced binary tree include AVL tree, Red-Black Tree, 2/3 Tree etc. The total number of nodes = 2 h + 1 - 1, where h is the height of the tree.Ī balanced binary tree is a binary tree where the height of the left and the right subtree is differed by at most 1.The number of leaf nodes = (n + 1)/2, where n is the total number of nodes.The number of internal nodes is the floor of n/2, where n is the total number of nodes.Ī perfect binary tree is a tree where all the interior nodes have 2 children and all the leaf nodes are on the same level.The last level of a complete binary treeĬan have 1 to 2 h nodes where h is the height of the tree. The nodes in the last level are filled from left to right. Complete Binary TreeĪ complete binary tree is a tree in which every level, except possibly the last, is filled. In a full binary tree, the number of leaf nodes = number of internal nodes + 1. Figure 2 shows an example of a full binary tree. The leaf nodes have 0 children and all other nodes have exactly 2 children. Full Binary TreeĪ full binary tree is a tree in which each node has either 0 or 2 children. Figure 1 is an example of a rooted binary tree. Each node in a rooted binary tree has at most 2 children. Rooted Binary TreeĪ binary tree with a root node and other nodes. Types of a binary treeĪll the major types of a binary tree are explained in detail below. The leaf nodes do not have any child nodes. When there is only one child we can call it left-child. The child node in the left of a node is called a left-child and the child node in the right is called a right-child. Figure 1 shows an example of a binary tree with 8 nodes. Binary trees are an extremely useful data structure in computer science. That means each node can have at most 2 child nodes. The binary trees are a type of tree where each node has maximum two degree.
0 Comments
Leave a Reply. |