binary trees summary trees consist of nodes (circlesconnected by edges (linesthe root is the topmost node in treeit has no parent in binary treea node has at most two children in binary search treeall the nodes that are left descendants of node have key values less than aall the nodes that are ' right descendants have key values greater than (or equal toa trees perform searchesinsertionsand deletions in (log ntime nodes represent the data objects being stored in the tree edges are most commonly represented in program by references to node' children (and sometimes to its parenttraversing tree means visiting all its nodes in some order the simplest traversals are preorderinorderand postorder an unbalanced tree is one whose root has many more left descendents than right descendantsor vice versa searching for node involves comparing the value to be found with the key value of nodeand going to that node' left child if the key search value is lessor to the node' right child if the search value is greater insertion involves finding the place to insert the new node and then changing child field in its new parent to refer to it an inorder traversal visits nodes in order of ascending keys preorder and postorder traversals are useful for parsing algebraic expressions when node has no childrenit can be deleted by setting the child field in its parent to null when node has one childit can be deleted by setting the child field in its parent to point to its child when node has two childrenit can be deleted by replacing it with its successor the successor to node can be found by finding the minimum node in the subtree whose root is ' right child in deletion of node with two childrendifferent situations arisedepending on whether the successor is the right child of the node to be deleted or one of the right child' left descendants