Binary Tree/ Binary Search Tree

Binary implies two. Binary trees have two children pointers, not necessarily with references to anything. Parent references are not necessary - that is up to implementation. \n\nIf nodes were mandatory to have both children elements, then the tree would be infinite and leaves would not exist. \n\nSo, options for a node are \n\n\nleaf \nleft/right child only\nboth children\n\n\nOf course, there are alternative ways to think about a \"tree\". For example, take the binary heap array implementation. \n\n",

It is not mandatory, you can create other types of links if you want. Define up and down pointers like this.\n\nFor a node x define up pointer u(x) as:\n\n\nif x is the right child, then u(x) is the parent of x\nif x is left child or root, then u(x) is the lowest node on the right path of x\n\n\nFor a node x define down pointer d(x) as:\n\n\nif x's left subtree does not exist, then d(x) = x\nif left subtree exists, then d(x) points to the rightmost node of x's left subtree\n\n\nThis is so called ring representation of a tree.",

Actually, there is nothing mandatory other than just one rule (i.e. the maximum number of children that any binary tree node can have is two). \n\nTechnically:\n\nEven a NULL is considered as a tree node when we define TreeNode *root = NULL. \nThough, it has no practical significance, we do pass them as argument while calling insert, delete and display methods. \n\nSo, as a coder, assuming that a binary tree will always comprise of at least a parent node can prove fatal if the sanity of root is not checked before processing a binary tree. ",