JAVA In many applications of trees, the nodes are generated as the tree is trave

Question

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.

Explanation / Answer

a)
For diagonal traversal, slope distance and mapping keys is used. For values mapping, vector need to be used.
Traverse tree and store the values into the map.

void diagonalTraverseUtil(Node* root, int d,
map<int, vector<int>> &diagonalTraversePrint)
{
// for head root
if (!root)
return;

// saving all nodes into vector
diagonalTraversePrint[d].push_back(root->data);

// for left child, increase slope
diagonalTraverseUtil(root->left, d + 1, diagonalTraversePrint);

// distance same
diagonalTraverseUtil(root->right, d, diagonalTraversePrint);
}

// printing the binary tree diagonal traversal
void diagonalTraversePrint(Node* root)
{
// mspping all nodes
map<int, vector<int> > diagonalTraversePrint;
diagonalTraverseUtil(root, 0, diagonalTraversePrint);
   //.. printing nodes
}

------------------------------------------------------------------------------------------------------------------------------------------------------
b)

Algorithm to count the nodes with one children.

function countNode(TreeNode t)
{
   if(t == null || countChildren(t)==0){
       return 0;
   }
   if(countChildren(t)==1){
       return 1+ countNode(t.getLeft()) + countNode(t.getRight());
   }
   if(countChildren(t)==2 ){
       return countNode(t.getLeft()) + countNode(t.getRight());
   }
   return 0;
}

function countChildren (TreeNode t){
int totalSingleChildNodes = 0;
if(t.getLeft() != null ) totalSingleChildNodes++;
if(t.getRight() != null) totalSingleChildNodes++;   
return totalSingleChildNodes;   
}

Related Questions

Navigate

• Browse (All)
• Browse J
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.