oneconnected to the given node (via an edgeon the level aboveis its parent for instancenode is the parent of node (and of node as wellnodes that have the same parent are known as siblings siblings areby definitionalways on the same level if node is the child of child of of another node then we say that the first node is descendent of the second node converselythe second node is an ancestor of the first node nodes which do not have any children are known as leaves ( the nodes labelled with and in figure path is sequence of connected edges from one node to another trees have the property that for every node there is unique path connecting it with the root in factthat is another possible definition of tree the depth or level of node is given by the length of this path hence the root has level its children have level and so on the maximal length of path in tree is also called the height of the tree path of maximal length always goes from the root to leaf the size of tree is given by the number of nodes it contains we shall normally assume that every tree is finitethough generally that need not be the case the tree in figure has height and size tree consisting of just of one node has height and size the empty tree obviously has size and is defined (convenientlythough somewhat artificiallyto have height - like most data structureswe need set of primitive operators (constructorsselectors and conditionsto build and manipulate the trees the details of those depend on the type and purpose of the tree we will now look at some particularly useful types of tree quad-trees quadtree is particular type of tree in which each leaf-node is labelled by value and each non-leaf node has exactly four children it is used most often to partition two dimensional space ( pixelated imageby recursively dividing it into four quadrants formallya quadtree can be defined to be either single node with number or value ( in the range to )or node without value but with four quadtree childrenlullruand rl it can thus be defined "inductivelyby the following rulesdefinition quad tree is either (rule root node with valueor (rule root node without value and four quad tree childrenlullruand rl in which rule is the "base caseand rule is the "induction stepwe say that quadtree is primitive if it consists of single node/numberand that can be tested by the corresponding conditionisvalue(qt)which returns true if quad-tree qt is single node to build quad-tree we have two constructorsbaseqt(value)which returns single node quad-tree with label value makeqt(luqtruqtllqtrlqt)which builds quad-tree from four constituent quadtrees luqtllqtruqtrlqt