Nios/treesize

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 child 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 the number of nodes in the tree rooted at the given node. The smallest possible tree has one node (both child pointers are null). You may assume root is always a valid tree.

unsigned int size (Node *root);


Expected solution length: Around 20 lines.

Sample Input

A[B,C], B[0,0], C[0,0]
A[0,0]

Sample Output

3
1

Write your solution here

Upload a source file...