this meansif tree has , , nodesthen its height is extended binary trees binary tree is said to be an extended binary tree (or -treeif each node in the tree has either no child or exactly two children figure shows how an ordinary binary tree is converted into an extended binary tree in an extended binary treenodes having two children are called ( (binternal nodes and nodes having no children are called external figure (abinary tree and (bextended nodes in fig the internal nodes are represented using circles binary tree and the external nodes are represented using squares to convert binary tree into an extended treeevery empty sub-tree is replaced by new node the original nodes in the tree are the internal nodesand the new nodes added are called the external nodes representation of binary trees in the memory in the computer' memorya binary tree can be maintained either by using linked representation or by using sequential representation linked representation of binary trees in the linked representation of binary treeevery node will have three partsthe data elementa pointer to the left nodeand pointer to the right node so in cthe binary tree is built with node type given below struct node struct node *leftint datastruct node *right}every binary tree has pointer rootwhich points to the root element (topmost elementof the tree if root nullthen the tree is empty consider the binary tree given in fig the schematic diagram of the linked representation of the binary tree is shown in fig in fig the left position is used to point to the left child of the node or to store the address of the left child of the node the middle position is used to store the data finallythe right position is used to point to the right child of the node or to store the address of the right child of the node empty sub-trees are represented using (meaning null figure linked representation of binary tree look at the tree given in fig note how this tree is represented in the main memory using linked list (fig