' left subtreewe will say is the left child of pand is the parent of lthe notion of right child is similar if node is left or right child of pwe say it is child of note that with the exception of the rootevery node has unique parent usuallybut not universallythe node object definition includes parent field (which is null for the rootobserve that for any node there exists unique sequence of nodes from the root to that node with each node in the sequence being child of the previous node this sequence is sometimes referred to as the search path from the root to the node the parent-child relationship defines an ancestor-descendant relationship on nodes in binary tree specificallya node is an ancestor of if it lies on the search path from the root to if node is an ancestor of dwe say is descendant of that node our convention is that node is an ancestor and descendant of itself node that has no descendants except for itself is called leaf the depth of node is the number of nodes on the search path from the root to nnot including itself the height of binary tree is the maximum depth of any node in that tree level of tree is all nodes at the same depth see figure on the preceding page for an example of the depth and height concepts as concrete examples of these conceptsconsider the binary tree in figure on the facing page node is the parent of and node is descendant of the search path to is haijkli the depth of is node is the node of maximum depthand hence the height of the tree is the height of the subtree rooted at is the height of the subtree rooted at is nodes dehmnand are the leaves of the tree full binary tree is binary tree in which every node other than the leaves has two children perfect binary tree is full binary tree in which all leaves are at the same depthand in which every parent has two children complete binary tree is binary tree in which every levelexcept possibly the lastis completely filledand all nodes are as far left as possible (this terminology is not universale some authors use complete binary tree where we write perfect binary tree it is straightforward to prove using induction that the number of nonleaf nodes in full binary tree is one less than the number of leaves perfect binary tree of height contains exactly + nodesof which are leaves complete binary tree on nodes has height blog nc left-skewed tree is tree in which no node has right childa right-skewed tree is tree in which no node has left child in either casewe refer to the binary tree as being skewed key computation on binary tree is traversing all the nodes in the tree (traversing is also sometimes called walking here are some ways in which this visit can be done traverse the left subtreevisit the rootthen traverse the right subtree (an inorder traversalan inorder traversal of the binary tree in figure on the preceding page visits the nodes in the following orderhdcebfhgajlmkniopi visit the roottraverse the left subtreethen traverse the right subtree ( preorder traversala preorder traversal of the binary tree in figure on the facing page visits the nodes in the following orderhabcdefghijklmnopi traverse the left subtreetraverse the right subtreeand then visit the root ( postorder traversala postorder traversal of the binary tree in figure on the preceding page visits the nodes in the following orderhdechgfbmlnkjpoiai let be binary tree of nodeswith height implemented recursivelythese traversals have (ntime complexity and (hadditional space complexity (the space complexity is dictated by the maximum depth of the function call stack if each node has parent fieldthe traversals can be done with ( additional space complexity