Binary Tree






A binary tree is made of nodes, where each node contains a "left" pointer, a "right" pointer, and a data element. The "root" pointer points to the topmost node in the tree. The left and right pointers recursively point to smaller "subtrees" on either side. A null pointer represents a binary tree with no elements -- the empty tree. The formal recursive definition is: a binary tree is either empty (represented by a null pointer), or is made of a single node, where the left and right pointers (recursive definition ahead) each point to a binary tree.
What is a Binary Tree
   
   A "binary search tree" (BST) or "ordered binary tree" is a type of binary tree where the nodes are arranged in order: for each node, all elements in its left subtree are less-or-equal to the node (<=), and all the elements in its right subtree are greater than the node (>). 

 Types of binary tree

  • A full binary tree which is also called as proper binary tree or 2-tree is a tree in which all the node other than the leaves has exact two children.
    • Full Binary Tree
  • A complete binary tree is a binary tree in which at every level, except possibly the last, has to be filled and all nodes are as far left as possible.
    • Complete Binary Tree
  • A binary tree can be converted into an extended binary tree by adding new nodes to its leaf nodes and to the nodes that have only one child. These new nodes are added in such a way that all the nodes in the resultant tree have either zero or two children. It is also called 2 - tree
  • The threaded Binary tree is the tree which is represented using pointers the empty subtrees are set to NULL, i.e. 'left' pointer of the node whose left child is empty subtree is normally set to NULL. These large numbers of pointer sets are used in different ways.

Advantages of binary tree :
  • It enables linear traversal of elements in the tree
  • Linear traversal eliminates the use of stacks which in turn consume a lot of memory space and computer time
  • It enables to find the parent of a given element without explicit use of parent pointers
  • Since nodes contain pointers to in-order predecessor and successor, the threaded tree enables forward and backward traversal of the nodes as given by in-order fashion

Comments

Post a Comment

Popular posts from this blog

AVL Tree & B Tree

Image
AVL Tree AVL tree is a self-balancing binary search tree in which each node maintains an extra information called as balance factor whose value is either -1, 0 or +1. AVL tree got its name after its inventor Georgy Adelson-Velsky and Landis. Balance Factor Balance factor of a node in an AVL tree is the difference between the height of the left subtree and that of right subtree of that node. Balance Factor = (Height of Left Subtree - Height of Right Subtree) or (Height of Right Subtree - Height of Left Subtree) The self balancing property of an avl tree is maintained by the balance factor. The value of balance factor should always be -1, 0 or +1. AVL Rotations Left Rotation If a tree becomes unbalanced, when a node is inserted into the right subtree of the right subtree, then we perform a single left rotation Right Rotation AVL tree may become unbalanced, if a node is inserted in the left subtree of the left subtree. The tree then needs a right
Read more

Data Structure Summary

Image
Linked List LinkedList  − A Linked List contains the connection link to the first link called First and to the last link called Last. Singly Linked List   A singly linked list is a set of nodes where each node has two fields ‘data’ and ‘link’. The ‘data’ field stores actual piece of information and ‘link’ field is used to point to next node. Doubly Linked List A doubly linked list  contains an extra pointer, typically called  previous pointer , together with next pointer and data which are there in singly linked list. Difference between Singly linked list and Doubly linked list In SingleLinkList, the traversal can be done using the next node link only. In DoublyLinkList, the traversal can be done using the previous node link or the next node link. The SingleLinkList occupies less memory than DoublyLinkList as it has only 2 fields. The DoublyLinkList occupies more memory than SingleLinkList as it has 3 fields. Less efficient access to elements. More efficient
Read more