## Circular Linked List Real Word Uses

##### The following are some real-world uses of a Circularly Linked List:

## A NumberList Linked ListA NumberList is a linked list used to represent the digits of a number. For |
example 983 | ||

is represented as: | |||

[ Node(9), Node(8), Node(3) ] | |||

Write the pseudocode for an algorithm which performs addition on 2 NumberLists, such | |||

that: |

##### Linked List with Small Modification

You are given a linked list with a small modification: in addition to the | next pointer, | ||

each node has a child pointer, which may or may not point to a separate list. | |||

These child lists may have one or more children of their own, and so on. | |||

The result is a multilevel linked data structure and an example is shown here: |

##### Algorithm Pseudocode to Flatten a Binary Tree

Write the pseudo-code for an algorithm to flatten the binary tree to a linked | list in place, | ||||

such that this tree would become: |

##### Recursive Implementation of a Function

In the lectures we discussed the recursive implementation of a function which computes | ||||||

the disk usage of a file system tree. In this DiskUsage tree, each node should hold the | ||||||

sum of the disk usage of all of its descendant | nodes. | The size of an empty DiskUsage | ||||

tree is 0, and a leaf node is also considered a DiskUsage tree. | ||||||

Here is an example: |

Write a recursive function which returns True if a tree is a valid DiskUsage tree and False otherwise.

// Recursively check if the sum of child nodes

// equates to the parent node's element

booleanisValidDiskUsage(Node currentNode) {

if(currentNode == null)

return true;

// Do bottom-up approach

for(inti = 0; i

if(!isValidDiskUsage(currentNode.childNodes.get(i)))

return false;

// Case for non-leaf nodes

if(currentNode.childNodes.size() > 0) {

int sum = 0;

for(inti = 0; i

sum = sum + currentNode.childNodes.get(i).element;

// non-leaf nodes should have matching sum

if(currentNode.element != sum)

return false;

}

// Case for leaf nodes, no validations needed

return true;

}

##### Two Nodes Function in a Binary Tree

You are familiar with the parent → child relationship in a binary tree.

Write a function which determines if two nodes in a binary tree are cousins.

Two nodes are cousins if they are on the same level and have different parents.

In the following example:

checkCousins("D", "C") = False

checkCousins("D", "F") = True

checkCousins("D", "B") = False

// Recursive method to find the parent of a key

Node findParentNode(Node current, String key) {

if(current == null)

return null;

if(current.left != null &¤t.left.element == key)

return current;

if(current.right != null &¤t.right.element == key)

return current;

Node parent = findParentNode(current.left, key);

if(parent != null)

return parent;

returnfindParentNode(current.right, key);

}

// Find which level a node is located in tree

intfindNodeLevel(Node current, String key, currentLevel) {

if(current == null)

return -1;

if(current.element == key)

returncurrentLevel;

intsubLevel = findNodeLevel(current.left, key, currentLevel + 1);

if(subLevel != -1)

returnsubLevel;

returnfindNodeLevel(current.right, key, currentLevel + 1);

}

// Check if 2 elements are cousins

// We assume rootNode is the start of the tree

booleancheckCousins(String key1, String key2) {

Node key1Parent = findParentNode(rootNode, key1);

Node key2Parent = findParentNode(rootNode, key2);

// Both key must exist in the tree

if(key1Parent == null || key2Parent == null)

return false;

// Both key must not have the same parent

if(key1Parent == key2Parent)

return false;

// Both key must be on the save level to be cousins

int key1Level = findNodeLevel(rootNode, key1, 0);

int key2Level = findNodeLevel(rootNode, key2, 0);

if(key1Level == key2Level)

return true;

return false;

}