JAVA

In many applications of trees, the nodes are generated as the tree is traversed rather than being fixed in advance. For example game trees that record all possible moves in a game such as chess are generated by game playing programs in this way. (Note that for this question we are considering general trees, not necessarily binary ones) Such trees may have infinite depth/height, which creates problems for the preorder, inorder, and postorder traversals. A level order traversal (visit the root, then the children of the root, then the children of the children and so on) can do better in this case: if every node has a finite number of children, then a level order traversal is guaranteed to reach any nominated node in a finite number of steps. However a level order traversal does not have this property if nodes can have infinitely many children. Explain how to design a method that performs a diagonal traversal on a tree: at any moment, a diagonal traversal has explored the subtree of any node to depth at most k, the second subtree to depth at most k-1, the third subtree to depth at most k-2 and so on. The figure below shows an example of such a traversal. The figure shows how the traversal could progress. The nodes shown in black have been visited at each time step shown (not all intermediate time steps are shown). Your answer must explain the diagonal traversal algorithm in a high-level way (the main idea of the traversal), and also explain the algorithm in pseudocode. Assume that the depth of the root is zero, if needed. Make your algorithm as efficient as possible. You are given a binary tree. Design an algorithm that will count the number of nodes in the tree that have exactly one child