the and in the name tree refer to how many links to child nodes can potentially be contained in given node for non-leaf nodesthree arrangements are possiblea node with one data item always has two children node with two data items always has three children node with three data items always has four children in shorta non-leaf node must always have one more child than it has data items orto put it symbolicallyif the number of child links is and the number of data items is dthen = + this is critical relationship that determines the structure of trees leaf nodeby contrasthas no childrenbut it can nevertheless contain onetwoor three data items empty nodes are not allowed because tree can have nodes with up to four childrenit' called multiway tree of order you may wonder why tree isn' called - tree can' node have only one childas nodes in binary trees cana binary tree (described in "binary trees,and "red-black trees"can be thought of as multiway tree of order because each node can have up to two children howeverthere' difference (besides the maximum number of childrenbetween binary trees and trees in binary treea node can have up to two child links single linkto its left or to its right childis also perfectly permissible the other link has null value in treeon the other handnodes with single link are not permitted node with one data item must always have two linksunless it' leafin which case it has no links figure shows the possibilities node with two links is called -nodea node with three links is -nodeand node with links is -nodebut there is no such thing as -node figure nodes in tree tree organization