Nios/treedepth

From ASMBits

A binary tree is a data structure composed of nodes that contain up to two child nodes each, with no cycles. (This is not a binary search tree, which additionally requires the children nodes to be ordered.)

This problem uses nodes that have two fields: Pointers to the two child nodes. There is no data field.

struct Node {
    Node *a;
    Node *b;
};

Starting at a node, the tree rooted at that node can be explored by recursively visiting each of its child nodes (if it is not a null pointer). A Node where both child pointers are 0 has no children (is a leaf node).

Write a function that returns whether the depth of the tree rooted at the given node is less than or equal to d (return 1 or 0). The depth is the number of hops needed to reach the furthest node from the root, including the root node itself. The smallest possible tree has depth 1 (if both child pointers are null). You may assume root is always a valid tree.

bool depth (Node *root, unsigned int d);

Remember: The initialization code you write for testing (at label _start) is not used during judging.

Expected solution length: Around 45 lines.

Sample Input

{A[B,C], B[0,0], C[0,0]}, 2
{A[0,0]}, 0

Sample Output

1 (true: depth is 2, which is <= 2)
0 (false: depth is 1, which is not <= 0)

The question is posed so that simply making function depth recursive wouldn't be enough to solve the problem. However, it can be easily split into two functions: 1. A function that compares the tree depth with d, and 2. a recursive function that returns the depth of the tree. Thus, you will likely be writing two functions for this problem.

Write your solution here

Upload a source file...