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]}, 0Sample Output
1 (true: depth is 2, which is <= 2) 0 (false: depth is 1, which is not <= 0)